JZOJ 5168. 冲击哥
JZOJ 5168. 冲击哥
题目
Description
Input
Output
Sample Input
1 3
Sample Output
ABA
Data Constraint
n,m≤100
题解
首先要明确题目的要求,可以理解成在矩阵中填上字母,使得相邻的相同字母连成的图形必须是正方形,满足字典序最小。
同时,所谓的“从上到下,从左到右”指的是:
ABC
AAA
ABC
不是AAABABCAC,而是ABCAAAABC,也就是不要想得太复杂。
既然要满足字典序最小,那么按字典序枚举每个格子,只要当前能放A就不放B,能放B就不放C……这样才能满足。
也就是贪心!
具体方式如下:
方式A、跟上下左右都不一样;
方式B、跟左边一样,扩大正方形。
形象一点(0为未填,1为当前枚举到的),
方式A:
ABAB
CC10
CC00
可以填成,
ABAB
CCB0
CC00
方式B:
A100
0000
0000
可以填成,
AA10
AA00
0000
继续填成,
AAA0
AAA0
AAA0
代码
#include<cstdio>
#include<cstring>
using namespace std;
char a[110][110];
int t[110][110];
int main()
{
int n,m,i,j,k;
char c;
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++) a[i][j]='-';
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) if(a[i][j]=='-')
{
for(c='A';c<='Z';c++)
{
if(c!=a[i][j-1]&&c!=a[i-1][j]&&c!=a[i+1][j]&&c!=a[i][j+1])
{
a[i][j]=c,t[i][j]=1;
break;
}
if(c!=a[i-1][j]&&c==a[i][j-1]&&i+t[i][j-1]<=n)
{
int p=1;
for(k=1;k<=t[i][j];k++) if(a[i+k-1][j+1]=='c') p=0;
if(p)
{
t[i][j]=t[i][j-1]+1;
for(k=1;k<=t[i][j];k++) a[i+k-1][j]=a[i+t[i][j]-1][j-t[i][j]+k]=c,t[i+k-1][j]=t[i][j];
break;
}
}
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) printf("%c",a[i][j]);
printf("\n");
}
return 0;
}