ACM 260 Il Gioco dell'X

一開始我有考慮到用DFS去搜尋，但是因為怕遞迴過深所以就作罷。後來要用Warshall's Algorithm去做，寫了一個半小時才發現這樣寫需要開(200*200) x (200*200)的陣列，所以宣告失敗= =去網路上找了一下解答，沒想到還真的直接用DFS去做就可以了-_-

#include <stdio.h>
#include <stdbool.h>

int n;
int move[6][2] = {
    {-1, -1}, {-1, 0}, {0, -1}, {0, 1}, {1, 0}, {1 ,1}
};
bool map[201][201], used[201][201], sol;

void dfs(int i, int j)
{
    if (i == n)
    {
        sol = true;
        return;
    }
   
    used[i][j] = true;
    int a, x, y;
    for (a = 0; a < 6; a++)
    {
        x = i+move[a][0];
        y = j+move[a][1];
        if (x <= n && x >= 1 && y <= n && y >= 1 && !used[x][y] && map[x][y])
        {
            dfs(x, y);
            if (sol)
                return;
        }
    }
}

int main(void)
{
    int i, j, k;
   
    k = 1;
    while (scanf("%d", &n) == 1 && n)
    {
        getchar();
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (getchar() == 'b')
                    map[i][j] = true;
                else
                    map[i][j] = false;
                used[i][j] = false;
            }
            getchar();
        }
        sol = false;
        for (j = 1; j <= n && !sol; j++)
                if (!used[1][j])
                    dfs(1, j);
        printf("%d ", k++);
        if (sol)
            printf("B\n");
        else
            printf("W\n");
    }
   
    return 0;
}