题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入输出格式
输入格式：
输入的第1行为两个正整数n，m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式：
输出包括m行，对于每个询问输出相应答案。
输入输出样例
输入样例#1：
2 2
01
10
1 1
2 2
输出样例#1：
4
4
说明
所有格子互相可达。
对于20%的数据，n≤10；
对于40%的数据，n≤50；
对于50%的数据，m≤5；
对于60%的数据，n≤100，m≤100；
对于100%的数据，n≤1000，m≤100000。
这道题必须记忆化搜索，要不然只有70分。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include<cstdio> #include<cstring> #include<queue> using namespace std; bool array[1001][1001]; bool visited[1001][1001]; int daarray[1001][1001]; int data[1000001]; int n, m; int dataptr; int BFS(int x, int y) { if (daarray[x][y] != -1) return data[daarray[x][y]]; queue < int >qx, qy; qx.push(x); qy.push(y); dataptr++; int total = 0; while (!qx.empty()) { x = qx.front(); y = qy.front(); qx.pop(); qy.pop(); if (x < 1 || x > n || y < 1 || y > n || visited[x][y]) continue; total++; daarray[x][y] = dataptr; visited[x][y] = true; if (array[x + 1][y] != array[x][y]) { qx.push(x + 1); qy.push(y); } if (array[x - 1][y] != array[x][y]) { qx.push(x - 1); qy.push(y); } if (array[x][y + 1] != array[x][y]) { qx.push(x); qy.push(y + 1); } if (array[x][y - 1] != array[x][y]) { qx.push(x); qy.push(y - 1); } } data[dataptr] = total; return total; } int main() { dataptr = 0; memset(daarray, -1, sizeof(daarray)); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%1d", &array[i][j]); for (int i = 1; i <= m; i++) { int x, y; int total = 0; scanf("%d%d", &x, &y); total = BFS(x, y); printf("%d\n", total); } } |
20180724更新：又做到这题，严格来说并非所谓的记忆化搜索，这里面有一个性质，即只要图中联通块中的点所对应的答案全都是一样的。利用这个性质去做题90分。所以对visited数组的memset清除也就不需要了（删除memset后AC）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> #include<functional> using namespace std; int n, m; int f[1005][1005]; int varr[1000005], vaptr = 0; char arr[1005][1005]; bool visited[1005][1005]; int step_x[4] = { 0,0,1,-1 }, step_y[4] = { 1,-1,0,0 }; inline void qpush(int v, int x, int y, queue<int>& qx, queue<int>& qy) { if (x>0 && y>0 && x <= n && y <= n && arr[x][y] - '0' == !v && !visited[x][y]) { qx.push(x); qy.push(y); } } inline int bfs(int x, int y) { if (f[x][y] != -1)return varr[f[x][y]]; //memset(visited, false, sizeof(visited)); vaptr++; queue<int> qx, qy; qx.push(x); qy.push(y); int cnter = 0; while (!qx.empty()) { x = qx.front(); y = qy.front(); qx.pop(); qy.pop(); if (visited[x][y])continue; f[x][y] = vaptr; visited[x][y] = true; cnter++; for (int i = 0; i<4; i++)qpush(arr[x][y] - '0', x + step_x[i], y + step_y[i], qx, qy); } return varr[vaptr] = cnter; } int main() { ios::sync_with_stdio(false); memset(f, -1, sizeof(f)); cin >> n >> m; for (int i = 1; i <= n; i++)cin >> arr[i] + 1; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; cout << bfs(x, y) << endl; } } |