又是水題,最近切題目只能切出水題。。。orz
給出一個聯通圖,要求在個點上染上兩種顏色,相鄰的點顏色不能相同,看能不能染色成功。
用dfs搜索一個點的每條邊,著色遞歸,如果已經染過色的且顏色出現矛盾就退出,用flag優化。
由於是聯通圖,不用考慮孤立的點或圖,就比較容易了。
據說可以用並查集做,額,估計要用加權。。。
代碼:
#include <cstdio> #include <cstdlib> #include <cstring> char maze[31][81]; void dfs(int x, int y) { maze[x][y] = '#'; if (maze[x - 1][y] == ' ') dfs(x - 1, y); if (maze[x][y - 1] == ' ') dfs(x, y - 1); if (maze[x + 1][y] == ' ') dfs(x + 1, y); if (maze[x][y + 1] == ' ') dfs(x, y + 1); } int main() { int n; // freopen("in", "r", stdin); scanf("%d", &n); gets(maze[0]); while (n--) { int i = 0; while (gets(maze[i]) && maze[i][0] != '_') { i++; }//input bool flag = true; for (int k = 0; k < i; k++) for (int j = 0; flag && j < strlen(maze[k]); j++) if (maze[k][j] == '*') { maze[k][j] = '#'; dfs(k, j); // printf("%d %d\n", k, j); flag = false; } // printf("%d %d\n", i, flag); for (int k = 0; k <= i; k++) puts(maze[k]); }//while } #include <cstdio> #include <cstdlib> #include <cstring> char maze[31][81]; void dfs(int x, int y) { maze[x][y] = '#'; if (maze[x - 1][y] == ' ') dfs(x - 1, y); if (maze[x][y - 1] == ' ') dfs(x, y - 1); if (maze[x + 1][y] == ' ') dfs(x + 1, y); if (maze[x][y + 1] == ' ') dfs(x, y + 1); } int main() { int n; // freopen("in", "r", stdin); scanf("%d", &n); gets(maze[0]); while (n--) { int i = 0; while (gets(maze[i]) && maze[i][0] != '_') { i++; }//input bool flag = true; for (int k = 0; k < i; k++) for (int j = 0; flag && j < strlen(maze[k]); j++) if (maze[k][j] == '*') { maze[k][j] = '#'; dfs(k, j); // printf("%d %d\n", k, j); flag = false; } // printf("%d %d\n", i, flag); for (int k = 0; k <= i; k++) puts(maze[k]); }//while }