记录编号	42390	评测结果	AAAAA
题目名称	84.画海岛地图	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2012-09-21 20:06:32	内存使用	1.94 MiB

#include <cstdio>
using namespace std;

struct rec
{
	int s[10],a[10][10];
};

int n,map[10][10],counter;

void dfs(int x,int y,int get,rec hang,rec lie)
{
	if (y>n)
	{
		int i,j,len,temp=0;
		for (i=1;i<=n;i++)
		{
			if (map[x][i])
			{
				j=i;
				while (map[x][j])
					j++;
				j--;
			}
			else
				continue;
			len=j-i+1;
			if (hang.a[x][temp]==len)
				temp++;
			else
				return;
			i=j;
		}
		if (hang.s[x])
			return;
		x++;
		y=1;
	}
	if (x>n)
	{
		if (get)
			return;
		int p,i,j,len,temp;
		for (p=1;p<=n;p++)
		{
			temp=0;
			for (i=1;i<=n;i++)
			{
				if (map[i][p])
				{
					j=i;
					while (map[j][p])
						j++;
					j--;
				}
				else
					continue;
				len=j-i+1;
				if (lie.a[p][temp]==len)
					temp++;
				else
					return;
				i=j;
			}
			if (lie.s[p])
				return;
		}
		counter++;
		printf("%d\n",counter);
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=n;j++)
				if (map[i][j])
					printf("*");
				else
					printf(" ");
				printf("\n");
		}
		return;
	}
	if (get)
	{
		if (!hang.s[x])
			return;
		if (!lie.s[y])
			return;
		map[x][y]=1;
		hang.s[x]--;
		lie.s[y]--;
	}
	dfs(x,y+1,1,hang,lie);
	dfs(x,y+1,0,hang,lie);
	map[x][y]=0;
}

int main(void)
{
	freopen("island.in","r",stdin);
	freopen("island.out","w",stdout);
	rec hang={0},lie={0};
	int i,temp;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		temp=0;
		scanf("%d",&hang.a[i][temp]);
		while (hang.a[i][temp])
		{
			hang.s[i]+=hang.a[i][temp];
			temp++;
			scanf("%d",&hang.a[i][temp]);
		}
	}
	for (i=1;i<=n;i++)
	{
		temp=0;
		scanf("%d",&lie.a[i][temp]);
		while (lie.a[i][temp])
		{
			lie.s[i]+=lie.a[i][temp];
			temp++;
			scanf("%d",&lie.a[i][temp]);
		}
	}
	dfs(1,1,1,hang,lie);
	dfs(1,1,0,hang,lie);
	if (!counter)
		printf("no\n");
	return(0);
}