UVA 12529 Fix the Pond（bfs）

題目大意：

                 給定2N *（2N+1）的地圖，地圖上有一些可以旋轉的門，至少要旋轉多少個門，使得可以從（1，1）經過

          所有的點最後到（1，2N+1）。

題解：

                 因為門是稀疏的，只有同奇同偶會有門，可以看出每個阻擋的門的旋轉不會在封閉新的塊。所以每個塊之間

         只要旋轉一個門就可以聯通了。最後就是求區域個數。

#include <iostream>   
#include<stdio.h>   
#include<memory.h>   
#include<vector>   
#include<memory.h>   
#include<map>   
using namespace std;  
#define N 650   
struct Node {  
    int x, y;  
} q[600100];  
int g[N][N][5], use[N][N];  
int cnt;  
char ch;  
int i, j, n;  
void BFS(int X, int Y, int c) {  
    use[X][Y] = c;  
    int st, ed, x, y;  
    st = 0;  
    ed = 1;  
    q[1].x = X;  
    q[1].y = Y;  
    while (st < ed) {  
        st++;  
        x = q[st].x;  
        y = q[st].y;  
        if (x - 1 >= 1) {  
            if (!use[x - 1][y] && g[x][y][0] == 1) {  
                ed++;  
                q[ed].x = x - 1;  
                q[ed].y = y;  
                use[x - 1][y] = c;  
            }  
        }  
        if (x + 1 <= 2 * n) {  
            if (!use[x + 1][y] && g[x][y][2] == 1) {  
                ed++;  
                q[ed].x = x + 1;  
                q[ed].y = y;  
                use[x + 1][y] = c;  
            }  
        }  
        if (y - 1 >= 1) {  
            if (!use[x][y - 1] && g[x][y][3] == 1) {  
                ed++;  
                q[ed].x = x;  
                q[ed].y = y - 1;  
                use[x][y - 1] = c;  
            }  
        }  
        if (y + 1 <= 2 * n + 1) {  
            if (!use[x][y + 1] && g[x][y][1] == 1) {  
                ed++;  
                q[ed].x = x;  
                q[ed].y = y + 1;  
                use[x][y + 1] = c;  
            }  
        }  
    }  
}  
char s[N];  
int main() {  
    while (scanf("%d", &n) != EOF) {  
        memset(use, 0, sizeof(use));  
        for (i = 1; i <= 2 * n; i++)  
            for (j = 1; j <= 2 * n + 1; j++)  
                g[i][j][0] = g[i][j][1] = g[i][j][2] = g[i][j][3] = 1;  
        for (i = 1; i < 2 * n; i++) {  
            scanf("%s", s);  
            int k = 0;  
            for (j = 1; j < 2 * n + 1; j++) {  
                if (((i & 1) && (j & 1)) || ((i & 1) == 0 && (j & 1) == 0)) {  
                    ch = s[k++];  
                    if (ch == 'V') {  
                        g[i][j][1] = 0;  
                        g[i][j + 1][3] = 0;  
                        g[i + 1][j][1] = 0;  
                        g[i + 1][j + 1][3] = 0;  
                    } else {  
                        g[i][j][2] = 0;  
                        g[i][j + 1][2] = 0;  
                        g[i + 1][j][0] = 0;  
                        g[i + 1][j + 1][0] = 0;  
                    }  
                }  
            }  
        }  
        cnt = 0;  
        for (i = 1; i <= 2 * n; i++)  
            for (j = 1; j <= 2 * n + 1; j++)  
                if (use[i][j] == 0) {  
                    ++cnt;  
                    BFS(i, j, cnt);  
                }  
  
        printf("%d\n", cnt - 1);  
    }  
    return 0;  
}