在遥远的西方有一个古老的王国,国王将他的王国分成了网格状,每一块称之为一个城市。在国王临死前,他将这些城市分给了自己的N个儿子(编号为0到N-1)。然而这N个王子的关系不是很好,0讨厌1,1讨厌2,2讨厌3……N-1讨厌0。
在国王死后,这种不好的关系使得王子之间爆发了战争。战斗只会在相邻的两个城市之间爆发(共有一条边称之为相邻),并且只有当A讨厌B时,A才会对B发起战斗,结果必定是A获得这次战斗的胜利。当一方胜利后,他所进攻的城市就会变成进攻方的。许多战斗是同时发生的,我们称之为一场战役。当多场战役发生之后,剩下的王子将不再发生战争。
例如,如果有3个王子,那么战斗过程如下所示:
第一行输入4个数,N,R,C,K。有N个王子,王国分为R*C的网格图。询问K场战役之后的城市归属图。
下面R行,每行C个数字,表示一开始城市的归属。
R行C列,表示K场战役之后的城市归属图。
Brother1.in
3 4 4 3
0 1 2 0
1 0 2 0
0 1 2 0
0 1 2 2
Brother2.in
4 2 3 4
1 0 3
2 1 2
Brother3.in
8 4 2 1
0 7
1 6
2 5
3 4
Brother1.out
2 2 2 0
2 1 0 1
2 2 2 0
0 2 0 0
Brother2.out
1 0 3
2 1 2
Brother3.out
7 6
0 5
1 4
2 3
2<=N<=100
2<=R,C<=100
1<=K<=100
保证数据合法
看到数据范围这么小,很显然可以直接按照题意模拟
复杂度\(O(4RCK)\)
#include<cstdio> #include<string> #define R register int #define N 105 #define ll long long #define inf 0x3f3f3f3f using namespace std; const int fx[4]={-1,1,0,0},fy[4]={0,0,-1,1}; int a[2][N][N],n,r,c,k; int max(int a,int b) {return a>b?a:b;} int min(int a,int b) {return a<b?a:b;} void read(int &x) { x=0;int f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f; } int main() { read(n);read(r);read(c);read(k);int x=0; for (R i=1;i<=r;++i) for (R j=1;j<=c;++j) read(a[x][i][j]); while (k--) { for (R i=1;i<=r;++i) for (R j=1;j<=c;++j) a[x^1][i][j]=a[x][i][j]; for (R i=1;i<=r;++i) for (R j=1;j<=c;++j) { for (R v=0;v<4;++v) if (i+fx[v]>0 && i+fx[v]<=r && j+fy[v]>0 && j+fy[v]<=c) if (a[x][i][j]+1==a[x][i+fx[v]][j+fy[v]] || a[x][i][j]==n-1 && a[x][i+fx[v]][j+fy[v]]==0) a[x^1][i+fx[v]][j+fy[v]]=a[x][i][j]; } x^=1; } for (R i=1;i<=r;++i) { for (R j=1;j<=c;++j) printf("%d ",a[x][i][j]); printf("\n"); } return 0; }