题意:给出 n*n的格子,把剩下的格子填上大写字母,使得任意两个相邻的格子的字母不同,且从上到下,从左到右的字典序最小
从A到Z枚举每个格子填哪一个字母,再判断是否合法
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=1000005; 17 18 int n; 19 char a[55][55]; 20 21 int okl(int x,int y,char ch){ 22 if(x-1 == -1 ) return 1; 23 if(a[x-1][y] == ch) return 0; 24 return 1; 25 } 26 27 int okr(int x,int y,char ch){ 28 if(x+1 == n ) return 1; 29 if(a[x+1][y] == ch) return 0; 30 return 1; 31 } 32 33 int oku(int x,int y,char ch){ 34 if(y-1 == -1 ) return 1; 35 if(a[x][y-1] == ch) return 0; 36 return 1; 37 } 38 39 int okd(int x,int y,char ch){ 40 if(y+1 == n ) return 1; 41 if(a[x][y+1] == ch) return 0; 42 return 1; 43 } 44 45 int main(){ 46 int T; 47 scanf("%d",&T); 48 int kase = 0; 49 while(T--){ 50 scanf("%d",&n); 51 for(int i = 0; i < n;i++) cin>> a[i]; 52 53 for(int i = 0;i < n;i++){ 54 for(int j =0;j < n;j++){ 55 for(char ch = 'A';ch <= 'Z';ch++){ 56 if(okl(i,j,ch) && okr(i,j,ch) && oku(i,j,ch) && okd(i,j,ch) && a[i][j] == '.') { 57 a[i][j] = ch; 58 break; 59 } 60 } 61 } 62 } 63 printf("Case %d: ",++kase); 64 for(int i = 0;i<n;i++) printf("%s ",a[i]); 65 } 66 return 0; 67 }