P1162 洛谷 填涂颜色

题目描述

思考

看数据量 30
而且是个二维的，很像走迷宫
直接深搜！
而且这个就是搜连通块

代码

一开始的15分代码，想的很简单，对dfs进行分类，如果是在边界上，就直接递归，不让其赋值，不在边界上赋值，但有个问题
你在 DFS 过程中尝试“边遍历边判断是否被圈住”，但这个信息在没有遍历完全之前是无法知道的。
举个测试点
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 0 0
错误输出
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 0 0
可以看到问题了吧

#include<bits/stdc++.h>using namespace std;const int N = 110;
int g[N][N];
int n;
bool st[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
void dfs(int x, int y)
{st[x][y] = true;for(int i = 0; i < 4; i++){int xx = x + dx[i], yy = y + dy[i];if(xx>1 && xx < n&& yy > 1 && yy < n && g[xx][yy] == 0 &&!st[xx][yy]) //不用st也可以{g[xx][yy] = 2;dfs(xx, yy);}else if((xx == 1 || xx == n || yy == 1 || yy == n )&&g[xx][yy] == 0 && !st[xx][yy])dfs(xx, yy);	}
}int main()
{cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){cin >> g[i][j];}}//开始搜连通块for(int i = 1; i <= n;i++){for(int j = 1; j <= n;j++){if(g[i][j] == 0 &&!st[i][j]) //这个直接相当于st标为已访问过了//不能直接标为已访问过了，因为0还分为两部分呢{
//				if(st[i][j] == true) //表示已访问过了
//				else	
//					dfs(i, j)
//				g[i][j] = 2; //先把自己变成2，后续就不搜了dfs(i, j);if(i == 1 || i == n || j == 1 || j == n)continue;g[i][j] = 2;}}}for(int i = 1; i <= n; i++){for(int j= 1; j <= n; j++)cout<<g[i][j]<<" ";cout<<endl;}return 0;
}

正解代码：把这个分为三部分，让求被围住的0，换个角度就是求边界0的连通块，把边界0的连通块替换为其他值，最后输出就好，这样做是因为我们一定知道边界的位置，知道从哪个点开始搜

#include <bits/stdc++.h>
using namespace std;const int N = 40;
int mapp[N][N];
//用dfs
int n;
bool state[N][N];void dfs(int x, int y)
{state[x][y] = true;mapp[x][y] = -1;int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};for(int i = 0; i < 4; i++){int a = x + dx[i];int b = y+ dy[i];if(a >= 1 && a<= n && b >= 1 && b <= n && !state[a][b] && mapp[a][b] == 0){state[a][b] = true;mapp[a][b] = -1;dfs(a, b);}}}int main()
{cin >> n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)cin >> mapp[i][j];for(int i = 1; i <= n; i++) //第一行if(mapp[1][i] == 0 && !state[1][i])dfs(1, i);for(int i= 1; i <= n; i++)  //最后一行if(mapp[n][i] == 0 && !state[n][i])	dfs(n, i);for(int i = 1; i <= n; i++)if(mapp[i][1] == 0 && !state[i][1])dfs(i, 1);for(int i =1; i <= n; i++)	if(mapp[i][n] == 0 && !state[i][n])dfs(i, n);for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(mapp[i][j] == -1){cout << "0"<<" ";}else if(mapp[i][j] == 0)cout <<"2"<<" ";elsecout << "1"<<" ";}cout << endl;}return 0;}

总结

有时候可以试着换位思考，类似于概率论里面求某个事情不发生的概率=1-发生的概率
想明白再做，不要尝试去钻牛角尖！！