Beyond the Void
BYVoid
USACO 4.4.3 Frame Up 重叠的图像 frameup

由题意可知,不存在一个矩形的一条边被完全覆盖,所以我们可以计算出矩形的坐标。 读入时记录矩形的每个点中最小x1,最小y1,最大x2,最大y2。可知左上角 (x1,y1) 右下角 (x2,y2) 右上角 (x2,y1) 左下角 (x1,y2)。

查找该矩形A边上,非该矩形的字母B,即覆盖矩形A被矩形B覆盖。建立一条有向边B->A,表示B是A的必要条件。然后进行拓扑排序,搜索求所有的拓扑序列,并排序输出。

注意,该题中的字母可能不连续,不要直接for(i=‘A’;i<=‘Z’;i++)。

USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: frameup
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3116 KB]
   Test 2: TEST OK [0.000 secs, 3112 KB]
   Test 3: TEST OK [0.011 secs, 3112 KB]
   Test 4: TEST OK [0.022 secs, 3112 KB]
   Test 5: TEST OK [0.011 secs, 3112 KB]
   Test 6: TEST OK [0.000 secs, 3116 KB]
   Test 7: TEST OK [0.011 secs, 3116 KB]
   Test 8: TEST OK [0.043 secs, 3116 KB]
   Test 9: TEST OK [0.162 secs, 3112 KB]

All tests OK.

Your program ('frameup') produced all correct answers!  This is your
submission #3 for this problem.  Congratulations!
/*
ID: cmykrgb1
PROG: frameup
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 'Z'+1
#define MAXA 10000
using namespace std;

ifstream fi("frameup.in");
ofstream fo("frameup.out");

typedef struct
{
	char m[26];
}Tans;

int N,M,len,acnt;
int map[30][30];
bool dis[MAX][MAX],usd[MAX],cu[MAX];
int x1[MAX],x2[MAX],y1[MAX],y2[MAX];
char L,start,use[MAX];
Tans ans[MAXA];

void init()
{
	int i,j,k;
	char c,p;
	memset(x1,1,sizeof(x1));
	memset(y1,1,sizeof(y1));
	fi >> N >> M;
	c=fi.get();
	for (i=0;i<N;i++)
	{
		for (j=0;j<M;j++)
		{
			map[i][j]=c=fi.get();
			cu[c]=true;
			if (c>L) L=c;
			if (i<x1[c]) x1[c]=i;
			if (j<y1[c]) y1[c]=j;
			if (i>x2[c]) x2[c]=i;
			if (j>y2[c]) y2[c]=j;
		}
		c=fi.get();
	}

	len=0;
	for (c='A';c<=L;c++)
	{
		if (!cu[c]) continue;
		len++;
		k=0;
		i=x1[c];
		for (j=y1[c];j<=y2[c];j++)
		{
			p=map[i][j];
			if (p!=c)
			{
				dis[p][c]=true;
				k++;
			}
		}
		i=x2[c];
		for (j=y1[c];j<=y2[c];j++)
		{
			p=map[i][j];
			if (p!=c)
			{
				dis[p][c]=true;
				k++;
			}
		}
		j=y1[c];
		for (i=x1[c]+1;i<=x2[c]-1;i++)
		{
			p=map[i][j];
			if (p!=c)
			{
				dis[p][c]=true;
				k++;
			}
		}
		j=y2[c];
		for (i=x1[c]+1;i<=x2[c]-1;i++)
		{
			p=map[i][j];
			if (p!=c)
			{
				dis[p][c]=true;
				k++;
			}
		}

		if (k==0)
			start=c;
	}
}

bool noprefix(char c)
{
	char p;
	for (p='A';p<=L;p++)
	{
		if (!cu[p]) continue;
		if (dis[p][c] && !usd[p])
			return false;
	}
	return true;
}

void dfs(char c,int k)
{
	if (k==len)
	{
		int i;
		acnt++;
		for (i=0;i<k;i++)
			ans[acnt].m[i]=use[k-i-1];
		return;
	}

	usd[c]=true;
	char p;
	for (p='A';p<=L;p++)
	{
		if (!cu[p]) continue;
		if (!usd[p] && noprefix(p))
		{
			use[k]=p;
			dfs(p,k+1);
		}
	}
	usd[c]=false;
}

int cmp(const void *a,const void *b)
{
	return strcmp( (*(Tans *)a).m , (*(Tans *)b).m ); 
}

void print()
{
	int i;
	qsort(ans+1,acnt,sizeof(ans[0]),cmp);
	for (i=1;i<=acnt;i++)
		fo << ans[i].m << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	for (start='A';start<=L;start++)
	{
		if (!cu[start] || !noprefix(start)) continue;
		use[0]=start;
		dfs(start,1);
	}
	print();
	return 0;
}

上次修改时间 2017-05-22

相关日志