首页 > 代码库 > Uva 11520 填充正方形

Uva 11520 填充正方形

2024-09-14 11:31:02   217人阅读

题目链接：https://vjudge.net/problem/UVA-11520

题意：

给定一个n*n的正方形，把剩下的格子中填满大写字母，任意两个相邻的格子字母不同，要求最后字典序最小；

 

分析：

第一想法回溯啊，当然是不对的，100个点回溯会死人的！

其实，可以发现，每个点不可能说，由于前面的决策，后来不能满足了，相邻的点有4个，我有26个英文字母。

技术分享
 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int maxn = 10 + 5; 6 int n; 7 char maps[maxn][maxn]; 8  9 10 int main()11 {12     int t;13     scanf("%d",&t);14     int kase = 1;15     while(t--) {16         scanf("%d",&n);17         for(int i=0;i<n;i++)18             scanf("%s",maps[i]);19 20         for(int i=0;i<n;i++) {21             for(int j=0;j<n;j++) {22                 if(maps[i][j]==‘.‘) {23                     for(char ch=‘A‘;ch<=‘Z‘;ch++) {24                         bool ok = true;25                         if(i>0&&maps[i-1][j]==ch) ok = false;26                         if(i<n-1&&maps[i+1][j]==ch) ok = false;27                         if(j>0&&maps[i][j-1]==ch) ok = false;28                         if(j<n-1&&maps[i][j+1]==ch) ok = false;29                         if(ok) {maps[i][j] = ch;break;}30                     }31                 }32             }33         }34 35         printf("Case %d:\n",kase++);36         for(int i=0;i<n;i++)37             printf("%s\n",maps[i]);38 39     }40     return 0;41 }
View Code

 

Uva 11520 填充正方形


联系
我们