1101: 填充正方形

Time Limit: 1 SecMemory Limit: 128 MB

Submit: 463Solved: 157

[Submit][Status][Web Board]

Description

在一个n*n的网格中填写了一些大写字母,你的任务是把剩下的格子中也填满大写字母,使得任意相邻格子中的字母不同.如果有多种填法,则要求按照从上到下,从左到右的顺序把所有格子连起来得到的字符串的字典序应最小.

Input

多组测试数据,每组测试数据的第一行为一个正整数n.(1<=n<=10),接下来n行分别有n个字符代表n*n的网格,为了清晰起见,用’.’代表没有大写字母的网格.

Output

对于每组数据输出填满大写字母后的网格.每组测试数据间有一个空行,最后一组测试数据后面没有空行.

Sample Input

3

...

...

...

3

...

A..

...

Sample Output

ABA

BAB

ABA

BAB

ABA

BAB

---

#include<iostream>

#include<cstdio>

using namespace std;

const int maxn=15;

char list[27]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void fill(char s[][maxn],int i,int j,int n)

{

int k=0;

for(k=0;k<26;k++)

{

if(i-1>=0 && s[i-1][j]==list[k])

continue;

if(j-1>=0 && s[i][j-1]==list[k])

continue;

if(j+1<=n-1 && s[i][j+1]==list[k])

continue;

if(i+1<=n-1 && s[i+1][j]==list[k])

continue;

s[i][j]=list[k];

return ;

}

}

int main()

{

int n,flag=0;

while(~scanf("%d",&n))

{

if(flag)cout<<endl;

char s[maxn][maxn];

for(int i=0;i<n;i++)

cin>>s[i];

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

if(s[i][j]=='.')

fill(s,i,j,n);

for(int i=0;i<n;i++)

cout<<s[i]<<endl;

flag=1;

}

return 0;

}