点击打开链接uva 11520
思路:dfs
分析:
1 题目给定一个n*n的地图,这个地图上面是一些空格和大写字母,现在要求把这个地图填满并且使得这个地图有最小的字典序
2 很明显的搜索题,我们只要通过枚举这个地图找到一个空格就进行dfs填充,最后得到的肯定是最小的字典序
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
char map[N][N];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
//判断当前字母是否满足
bool ok(int x , int y , int n , char ch){
bool mark = true;
for(int i = 0 ; i < 4 ; i++){
int tmpx = x+dir[i][0];
int tmpy = y+dir[i][1];
if(tmpx >= 0 && tmpy < n && map[tmpx][tmpy] == ch)
mark = false;
}
return mark;
}
void dfs(int x , int y , int n){
if(map[x][y] != '.')
return;
for(int i = 65 ; i < 65+26 ; i++){
if(ok(x , y , n , i)){
map[x][y] = i;
break;
}
}
for(int i = 0 ; i < 4 ; i++){
int tmpx = x+dir[i][0];
int tmpy = y+dir[i][1];
if(tmpx >= 0 && tmpy < n)
dfs(tmpx , tmpy , n);
}
}
void solve(int n){
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
if(map[i][j] == '.')
dfs(i , j , n);
}
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)
printf("%c" , map[i][j]);
printf("\n");
}
}
int main(){
int n , T , Case = 1;
scanf("%d" , &T);
while(T--){
scanf("%d%*c" , &n);
for(int i = 0 ; i < n ; i++)
gets(map[i]);
printf("Case %d:\n" , Case++);
solve(n);
}
return 0;
}
分享到:
相关推荐
Uva 100 ,问题是The 3n+1 probelm ,可以ac的代码
UVA 10474
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)