P1162 填涂颜色

填涂颜色 - 洛谷

这个题用逆向思维，见不用染色的地方标记。

这里为了处理一些情况，将图周围一圈的0空出来，用于吧围墙之外的部分都标记上

用宽搜，四联通，感觉好奇怪，八连通ac不了

#include <iostream>
#include <cstring>
#include <queue>using namespace std;typedef pair<int, int> PII;
const int N = 35;
int n, c;
int g[N][N];
bool st[N][N];
queue<PII> q;void bfs()
{st[0][0] = false;q.push({0, 0});int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};while(q.size()){auto t = q.front();q.pop();for(int i = 0; i < 4; i ++ ){int a = t.first + dx[i], b = t.second + dy[i];if(a < 0 || a > n + 1 || b < 0 || b > n + 1) continue;if(g[a][b]) continue;if(!st[a][b]) continue;st[a][b] = false;q.push({a, b});}}
}int main()
{cin >> n;for(int i = 0; i <= n + 1; i ++ )memset(st[i], true, sizeof st[i]);for(int i = 1; i <= n; i ++ )for(int j = 1; j <= n; j ++ )cin >> g[i][j];bfs();for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= n; j ++ ){if(st[i][j] && !g[i][j])g[i][j] = 2;}}for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= n; j ++ ){printf("%d ", g[i][j]);}printf("\n");}return 0;
}