uva 11520 Fill the Square

点击打开链接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;
}