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;
}
补充：软件开发 , C++ ,
