URAL 1033 Labyrinth

URAL_1033

    要注意下两个entrance不一定是连通的，然后用dfs计数就可以了。

#include<stdio.h>
#include<string.h>
#define MAXD 40
int N, g[MAXD][MAXD], vis[MAXD][MAXD];
char b[MAXD];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
void init()
{
    int i, j, k;
    memset(g, 0, sizeof(g));
    for(i = 1; i <= N; i ++)
    {
        scanf("%s", b + 1);
        for(j = 1; j <= N; j ++)
            if(b[j] == '.')
                g[i][j] = 1;
    }
}
void dfs(int x, int y, int &ans)
{
    int i, newx, newy;
    vis[x][y] = 1;
    for(i = 0; i < 4; i ++)
    {
        newx = x + dx[i], newy = y + dy[i];
        if(!g[newx][newy])
                ++ ans;
        else if(!vis[newx][newy])
            dfs(newx, newy, ans);
    }
}
void solve()
{
    int i, j, k, ans = 0;
    memset(vis, 0, sizeof(vis));
    dfs(1, 1, ans);
    if(!vis[N][N])
        dfs(N, N, ans);
    printf("%d\n", (ans - 4) * 9);
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
    return 0;
}