题意
填充一个NxN网格，使得每个格子的字母与其相邻的字母均不相同。输出字典序最小的填充方案。
思路
注意到解的空间非常大，因此只要每一次从’a’~’z’枚举并检查当前格子就可以了。这样也可以保证字典序最小，因为每一次的填充是从最小的字母开始尝试的。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; char board[11][11]; int n; int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}}; void input(){ memset(board,0,sizeof(board)); scanf(" %d",&n); for(int i = 1; i<= n; i++){ for(int j = 1; j <= n; j++){ scanf(" %c",&board[i][j]); } } } void output(){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ putchar(board[i][j]); } puts(""); } } bool fillone(){ int y = 1,x = 1; bool mkr[26]; memset(mkr,0,sizeof(mkr)); int ori = 1; while(x <= n){ int stp = 1; while(stp <= n){ if(board[y][x] != '.'){ stp++; y += ori; }else{ for(int i = 0; i< 4; i++){ char cur = board[y + dir[i][0]][x+dir[i][1]]; if(isalpha(cur)){ mkr[cur - 'A'] = true; } } for(int i = 'A'; i <= 'Z'; i++){ if(!mkr[i-'A']){ board[y][x] = i; return true; } } } } y -= ori; ori *= -1; x++; } return false; } int main(){ int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++){ printf("Case %d:\n",d); input(); while(fillone()); output(); } return 0; } |
