MYF

UVa 11520 Fill the Square

Posted on | In | | Visitors

题目链接

UVa 11520

解题方法：水 (实在想不出来这叫什么方法)

题目分析

题目大意

给你一个n*n的方阵，把所有的’ . ‘换成字母。并且满足以下两个要求:

  • 任意两个相邻的字符不相同

  • 字母出现的方式按照字母序，并且出现的字母种类尽可能少

    • 然后输出全是字母的方阵。

    解析

    一开始以为是BFS，因为BFS层层扩散，结果WA了，呵呵。网上稍微搜了一下，发现直接一个位置一个位置的扫就好了。假设上下左右分别是a、b、c、d四个字母，所以到字母e怎么着也够了。定义了一个findit()，找符合要求的字符，然后扔到对应位置。全都扫一遍，搞定。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    #include <set>
    #include <map>
    #include <stack>
    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <iomanip>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define PI acos(-1)
    #define debug         printf("Hi----------\n")
    #define eps 1e-8
    #define INF 0x3f3f3f3f
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    typedef long long ll;
    using namespace std;
    #define maxn 10005
    char s[15][15];
    int t,n,cnt;
    int vis[15][15]={};
    int mx[]={1,-1,0,0};
    int my[]={0,0,1,-1};
    bool cango(int x,int y){
        return x>=1&&x<=10&&y>=1&&y<=10;
    }
    char findit(int x,int y){
        int t[5]={};
        for (int i=0; i<4; i++) {
            if (cango(x+mx[i], y+my[i])) {
                switch (s[x+mx[i]][y+my[i]]) {
                    case 'A': t[0]=1; break;
                    case 'B': t[1]=1; break;
                    case 'C': t[2]=1; break;
                    case 'D': t[3]=1; break;
                    default: break;
                }
            }
        }
        for (int i=0; i<5; i++) {
            if (t[i]==0) {
                return 'A'+i;
            }
        }
        return 0;
    }
    int main(){
        scanf("%d",&t);
        for (int cas=1; cas<=t; cas++) {
            scanf("%d",&n);
            for (int i=1; i<=n; i++) {
                scanf("%s",s[i]+1);
            }
            
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    if (s[i][j]=='.') {
                        s[i][j]=findit(i,j);
                    }
                }
            }
            
            printf("Case %d:\n",cas);
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    printf("%c",s[i][j]);
                }
                printf("\n");
            }
        }
    }