本文主要是介绍ZOJ3810(2014年牡丹江网络赛B题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
网络赛中我做的惟一一题……
题意大致就是将n^2个格子分成面积相同但形状不同的n部分，每部分要连通，且整个区域能用不超过四种颜色染色。
很明显的构造题，构造方法要写还蛮麻烦的，还是直接上代码好了……
当然记住要特判n=1的情况，网络赛时因为这个WA了一次……
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[105][105];
char c[10]="ARGBY";
int main()
{int i,j,n,T,sg,cur;scanf("%d",&T);while(T--){scanf("%d",&n);if(n==1) printf("G\n");else if(n<5) printf("No solution!\n");else{memset(a,0,sizeof(a));for(i=1;i<=n;i++) a[i][1]=1;sg=-1;cur=2;for(i=1;i<=n/2;i++){for(j=2;j<=n;j++) if(!a[n+1-i][j]) a[n+1-i][j]=cur;if(sg>0) for(j=2;j<=i+1;j++) a[n-i][j]=cur;else for(j=n;j>=n-i+1;j--) a[n-i][j]=cur;sg=-sg;cur++;if(cur>=5) cur=2;}int nt=-1,dir;for(i=(n+1)/2;i>=3;i--){nt=-1;for(j=2;j<=n;j++){if(!a[i][j]&&nt<0) {nt=j;dir=(j==2);}if(!a[i][j]) a[i][j]=cur;}if(dir) for(j=n;j>=2;j--) {a[i-1][j]=cur;if(a[i][j]==cur) break;}else for(j=2;j<=n;j++) {a[i-1][j]=cur;if(a[i][j]==cur) break;}cur++;if(cur>=5) cur=2;}if(!a[2][2]) {a[1][n]=(cur-1==1?4:cur-1);a[3][2]=0;}else {a[1][2]=(cur-1==1?4:cur-1);a[3][n]=0;}if(n==5) cur=3; else if(n==6) cur=4;for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(!a[i][j]) a[i][j]=cur;for(i=1;i<=n;i++,printf("\n")) for(j=1;j<=n;j++) printf("%c",c[a[i][j]]);}}return 0;
}这篇关于ZOJ3810(2014年牡丹江网络赛B题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
