一条搜索水题，竟然交了10次才a...还是太菜了，怒献一篇题解，思路是记忆化dfs+剪枝。
先看一下题目：(截图拼接的，中间有一条丑陋的线)
image
思路
- 先说一说我自己的思路，这道题一眼看上去就是一个深搜，把01用二维数组存下下来，搜索每一个格子然后判断合理情况，记录格子能联通的最大块数，本以为是水题，噼里啪啦一顿dfs交上去，TLE了三个点只有70分，来看看这样做的代码：
有几个注意点提一下：
- cnt记录当前搜索的起始格子能联通的最大块数
- dir数组记录下一步的四个不同走向
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
int ans[100100];
char maze[maxn][maxn];
int n, m, cnt;
int vis[maxn][maxn];
int dir[4][2] = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};
void dfs(int x, int y, int cur){
vis[x][y] = 1;
cnt++;
for (int i = 0; i < 4; ++i){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx < 0 || xx >= n || yy < 0 || yy >= n || vis[xx][yy])
continue;
int next = maze[xx][yy] - '0';
if (next == !cur){
dfs(xx, yy, next);
}
}
}
int main(int argc, char const *argv[]){
int top = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i){
scanf("%s", maze[i]);
}
for (int i = 0; i < m; ++i){
int x, y;
scanf("%d%d", &x, &y);
dfs(x-1, y-1, maze[x-1][y-1] - '0');
ans[top++] = cnt;
cnt = 0;
memset(vis, 0, sizeof(vis));
}
for (int i = 0; i < top; ++i){
printf("%d\n", ans[i]);
}
return 0;
}
- 这样做问题出在哪里呢？我把测试数据看了一下，发现很恶心，n和m分别取到了1000和10000，那显然，memset是很耗时间的，于是我想到把vis数组的标记改为layer，代表所搜索的格子所在的不同联通块。这样，每一次去数新一个格子所能联通的块数就只要更新layer，节省了很大一块时间，成功过掉了第二个点也就是n=1000, m=10000的点，下面是改良后的80分的代码：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
int ans[100100];
char maze[maxn][maxn];
int n, m, cnt, layer=1;
int vis[maxn][maxn], record[maxn][maxn];
int dir[4][2] = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};
void dfs(int x, int y, int cur){
vis[x][y] = layer;
cnt++;
for (int i = 0; i < 4; ++i){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx < 0 || xx >= n || yy < 0 || yy >= n || vis[xx][yy] == layer)
continue;
int next = maze[xx][yy] - '0';
if (next == !cur){
dfs(xx, yy, next);
}
}
}
int main(int argc, char const *argv[]){
int top = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i){
scanf("%s", maze[i]);
}
for (int i = 0; i < m; ++i){
int x, y;
scanf("%d%d", &x, &y);
dfs(x-1, y-1, maze[x-1][y-1] - '0');
ans[top++] = cnt;
cnt = 0;
layer++;
}
for (int i = 0; i < top; ++i){
printf("%d\n", ans[i]);
}
return 0;
}
- 到了这里，我当时已经想不到其他优化方法了，于是怀疑自己是否用错了方法，也有大佬告诉我这题实际上用广搜随便写，或者并查集加滚动数组，但我不信邪啊...本着锻炼自己dfs+记忆的能力的想法，我苦苦思索，是与否有其他优化方法，果然，有一条很明显的但是一早就被我忽略了：
同一个联通块所在的格子，能到达的格子数都是相同的。
这样一看，怎么记忆化就已经很明显了，我们已经用vis数组标记过了当前搜索的格子所在的联通块，用layer表示，那么我们只要再开一个record数组，将已经遍历过的联通块对应的格子数记录下来，那么搜索到相应联通块里的其它格子时，就不用再搜索了，这是一步很大的优化，最终我提交了修改过的代码，100分ac，代码如下：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
const int maxm = 100100;
int ans[maxm];
char maze[maxn][maxn];
int n, m, cnt, layer=1;
int vis[maxn][maxn], record[maxm];
int dir[4][2] = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};
void dfs(int x, int y, int cur){
vis[x][y] = layer;
record[layer] = ++cnt;
for (int i = 0; i < 4; ++i){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx < 0 || xx >= n || yy < 0 || yy >= n || vis[xx][yy] == layer)
continue;
int next = maze[xx][yy] - '0';
if (next == !cur){
dfs(xx, yy, next);
}
}
}
int main(int argc, char const *argv[]){
memset(record, -1, sizeof(record));
int top = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i){
scanf("%s", maze[i]);
}
for (int i = 0; i < m; ++i){
int x, y;
scanf("%d%d", &x, &y);
if (record[vis[x-1][y-1]] == -1){
dfs(x-1, y-1, maze[x-1][y-1] - '0');
ans[top++] = record[vis[x-1][y-1]];
}else {
ans[top++] = record[vis[x-1][y-1]];
}
cnt = 0;
layer++;
}
for (int i = 0; i < top; ++i){
printf("%d\n", ans[i]);
}
return 0;
}
洛谷的界面做的还是很漂亮的。
image
