UVA 11520 填充正方形

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2515

http://7xjob4.com1.z0.glb.clouddn.com/c6a2a6f54f5a6c2cae2c82df2ec552f7

题意：填已有字母的格子，使相邻格子字母不同，使字典序尽量小

思路：从小到大排，检验是否可行

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 char grid[15][15];
 6 
 7 int main()
 8 {
 9     int T,i,j,cas=1;
10     scanf("%d",&T);
11     while(T--)
12     {
13         scanf("%d",&n);
14         for(i=0;i<n;i++)
15         {
16             scanf("%s",grid[i]);
17         }
18         for(i=0;i<n;i++)
19         {
20             for(j=0;j<n;j++)
21             {
22                 if(grid[i][j]=='.')
23                 {
24                     for(char ch='A';ch<='Z';ch++)
25                     {
26                         bool flg=true;
27                         if(i-1>=0 && grid[i-1][j]==ch)  flg=false;
28                         if(i+1<n && grid[i+1][j]==ch)   flg=false;
29                         if(j-1>=0 && grid[i][j-1]==ch)  flg=false;
30                         if(j+1<n && grid[i][j+1]==ch)   flg=false;
31                         if(flg)
32                         {
33                             grid[i][j]=ch;
34                             break;
35                         }
36                     }
37                 }
38             }
39         }
40 
41         printf("Case %d:
",cas++);
42         for(i=0;i<n;i++)
43         {
44             printf("%s
",grid[i]);
45         }
46     }
47     return 0;
48 }

View Code