现在的位置: 首页 > 算法 > 正文

The 2014 ACM-ICPC Asia Mudanjiang Regional First Round B&&zoj3810

2019年02月28日 算法 ⁄ 共 2996字 ⁄ 字号 评论关闭

//题意:把n*n分成n个形状不一样的图形,用G.Y,B,R给这些矩形上色(如果相邻俩个图形颜色一样,就和并在一起了,不成立),存在输出n*n的矩形(用G,Y,B,R表示),不存在输出No solution!;

//思路:2,3,4不成立,6要自己构造,其它基本都是一个思路,大致上图片的意思,具体思路大家输出来看看,我也不知道该怎么描述;

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int vis[110][110],a[110][110],n;
void fuck1()
{
	for(int ii=1;ii<=n/2;ii++)//7
	{
		int i=n,j=ii;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
	int i=n/2+2,j=n/2+1;
	int num=0;
	while(1)
	{
		a[i][j]=4;
		if(a[i-1][j]==0)
			i--;
		else
			j++;

		num++;
		if(num==n)
			break;
	}
	for(int ii=(n-1)/2+3;ii<=n;ii++)
	{
		int i=n,j=ii-2;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
}
void fuck2()
{
	for(int ii=1;ii<=n/2;ii++)//9
	{
		int i=n,j=ii;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
	int i=n/2+2,j=n/2+1;
	int num=0;
	while(1)
	{
		a[i][j]=4;
		if(a[i-1][j]==0)
			i--;
		else
			j++;
		num++;
		if(num==n)
			break;
	}
	for(int ii=(n-1)/2+3;ii<=n;ii++)
	{
		int i=n,j=ii-2;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
}
void fuck3()
{
	for(int ii=1;ii<=n/2;ii++)//10
	{
		int i=n,j=ii;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
	int i=n/2+2,j=n/2+1;
	int num=0;
	while(1)
	{
		a[i][j]=4;
		if(a[i-1][j]==0)
			i--;
		else
			j++;

		num++;
		if(num==n)
			break;
	}
	for(int ii=n/2+3;ii<=n;ii++)
	{
		int i=n,j=ii-2;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
}
void fuck4()
{
	for(int ii=1;ii<=n/2;ii++)//8
	{
		int i=n,j=ii;
		int num=0;
		while(1)
		{
			if(ii%2==1)
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}
	int i=n/2+2,j=n/2+1;
	int num=0;
	while(1)
	{
		a[i][j]=4;
		if(a[i-1][j]==0)
			i--;
		else
			j++;
		num++;
		if(num==n)
			break;
	}
	for(int ii=n/2+3;ii<=n;ii++)
	{
		int i=n,j=ii-2;
		int num=0;
		while(1)
		{
			if(ii%2==0)
			{
				a[i][j]=3;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			else
			{
				a[i][j]=2;
				if(a[i-1][j]==0)
					i--;
				else
					j++;
			}
			num++;
			if(num==n)
				break;
		}
	}

}
int main ()
{
	int t;
	while(scanf("%d",&t)!=EOF)
	{
		while(t--)
		{
			memset(a,0,sizeof(a));
			scanf("%d",&n);
			if(n==1)
				printf("Y\n");
			else if(n==2||n==3||n==4)
				printf("No solution!\n");
			else if(n==6)
			{
				printf("YYYYYY\n");
				printf("RRBBBB\n");
				printf("YRRRRB\n");
				printf("YYBBGB\n");
				printf("YYBBGG\n");
				printf("YBBGGG\n");
			}
			else
			{
				memset(a,0,sizeof(a));
				for(int i=1;i<=n;i++)
					a[1][i]=1;
				if(n%2==1)//奇数
				{
					if((n/2)%2==1)//7
						fuck1();
					else//9
						fuck2();
				}
				else
				{
					if((n/2)%2==1)//10
						fuck3();
					else//8
						fuck4();
				}
				for(int i=1;i<=n;i++)
				{
					for(int j=1;j<=n;j++)
					{
						//printf("%d",a[i][j]);
						if(a[i][j]==1)
							printf("Y");
						else if(a[i][j]==2)
							printf("G");
						else if(a[i][j]==3)
							printf("R");
						else if(a[i][j]==4)
							printf("B");
					}
					printf("\n");
				}
			}
		}
	}
	return 0;
}

//过程:写的都是泪,比赛就写了5个小时,结束后有了思路继续写,再搞了3小时(卧槽,中途还打了场cf,我的小心脏怎么受的了)
//感悟:这道题目告诉我,以后分类(暴力)的东西最好用函数分开,不然自己都乱了,更何况让队友改;

//贴代码,思路不是我的,我也不知道别人怎么想出来的,orz,这群985,211,的简直凶残,

【上篇】
【下篇】

抱歉!评论已关闭.