填涂顏色 - 洛谷

這個(gè)題用逆向思維，見不用染色的地方標(biāo)記。

這里為了處理一些情況，將圖周圍一圈的0空出來(lái)，用于吧圍墻之外的部分都標(biāo)記上

用寬搜，四聯(lián)通，感覺好奇怪，八連通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;
}