UVA11520填充正方形

UVA11520

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

【题目描述】：填充正方形

N*N的网格，某些地方填充了一些大写字母，让你在空下的地方填上’A’.....’Z’,使得从上到下，从左到右字典序最小。（N<=10）

【思路分析】：

【决策方案】：因为相互影响很难手动枚举，约等于26^(n^2)种。

【约束条件】：上下左右和中间的5快不能相同。

【目标评判标准】：字典需最小

【算法分析】：这道题目是赤裸裸的智商题（汗），上面的条件N<=10完全就是误导条件，让你向搜索剪枝方向想。因为我们有26个字母可选，最多剔除4个，所以一定能继续向下填，在这时，字典序优先就成为了一个充分条件了。所以从上往下，从左向右依次填即可。复杂度为O（5*n^2)

【完整代码】：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<math.h>
 7 #include<queue>
 8 #include<vector>
 9 //#include<map>
10 #define MAXN 10+5
11 #define MAXM 20000+5
12 #define oo 9556531
13 #define eps 0.000001
14 #define PI acos(-1.0)//这个精确度高一些
15 #define REP1(i,n) for(int i=0;i<=(n);i++)
16 #define REP2(i,n) for(int i=1;i<=(n);i++)
17 using namespace std;
18 
19 char map[MAXN][MAXN];
20 
21 char getM(int x,int y)
22 {
23     for(char i='A';i<='Z';i++)
24     {
25         if (i==map[x+1][y] || i==map[x-1][y] || i==map[x][y-1] || i==map[x][y+1]) continue;
26         return i;
27     }
28 }
29 
30 int cas,n;
31 int main()
32 {
33     cin>>cas;
34     for(int k=1;k<=cas;k++)
35     {
36         cin>>n;
37         REP1(i,n+1) REP2(j,n+1) map[i][j]='.';
38         REP2(i,n) REP2(j,n) cin>>map[i][j];
39         REP2(i,n) REP2(j,n) if (map[i][j]=='.') map[i][j]=getM(i,j);
40         cout<<"Case "<<k<<":"<<endl;
41         REP2(i,n) {REP2(j,n) cout<<map[i][j];cout<<endl;}
42     }
43     return 0;
44 }

关键词：思维