#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int map[50][50];
bool check[50];
int letterlist[50];
int stack[50];
int top,countletter,i,j,m,n;
char ch;
void print()
{
	int i;
	for (i=top;i>1;i--) {printf("%c",stack[i]+64);}
    printf("%c\n",stack[1]+64);
}

bool manzu(int cc,int &h1,int &h2,int &l1,int &l2)
{
	int i,j;
	bool bb;
	bb=false;
	for (i=1;i<=n;i++) if (bb==true){break;} else {for (j=1;j<=m;j++) if (map[i][j]==cc) { h1=i;bb=true;break;}}
	bb=false;
	for (i=n;i>h1;i--) if (bb==true){break;} else {for (j=1;j<=m;j++) if (map[i][j]==cc) { h2=i;bb=true;break;}}
	bb=false;
	for (i=1;i<=m;i++) if (bb==true){break;} else {for (j=1;j<=n;j++) if (map[j][i]==cc) { l1=i;bb=true;break;}}
	bb=false;
	for (i=m;i>l1;i--) if (bb==true){break;} else {for (j=1;j<=n;j++) if (map[j][i]==cc) { l2=i;bb=true;break;}}
	for (j=l1;j<=l2;j++) if (((map[h1][j]!=cc)&&(map[h1][j]!=-1))||((map[h2][j]!=cc)&&(map[h2][j]!=-1))) {return false;}
	for (i=h1;i<=h2;i++) if (((map[i][l1]!=cc)&&(map[i][l1]!=-1))||((map[i][l2]!=cc)&&(map[i][l2]!=-1))) {return false;}
	return true;
}


void dfs(int s)
{
	int i,p,q,i1,i2,j1,j2;
	bool bz;
	int tempmap[31][31];
	memset(tempmap,0,sizeof(tempmap));
	if (s==(countletter+1))
	{
		print();
	}
	else
	{
		for (i=1;i<=countletter;i++)
			if (check[letterlist[i]]==false)
			{
				bz=manzu(letterlist[i],i1,i2,j1,j2);
				if (bz==true)
				{
					top++;
					check[letterlist[i]]=true;
					stack[top]=letterlist[i];
					for (p=1;p<=n;p++) for (q=1;q<=m;q++) tempmap[p][q]=map[p][q];
					for (p=j1;p<=j2;p++){ map[i1][p]=-1;map[i2][p]=-1;}
					for (p=i1;p<=i2;p++){ map[p][j1]=-1;map[p][j2]=-1;}
					dfs(s+1);
					for (p=1;p<=n;p++) for (q=1;q<=m;q++) map[p][q]=tempmap[p][q];
					top--;
					check[letterlist[i]]=false;
				}
			}
	}
}

void init()
{
	memset(map,0,sizeof(map));
		memset(check,false,sizeof(check));
		memset(stack,0,sizeof(stack));
		top=0;
		countletter=0;
		int temp=0;
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=m;j++)
			{
				scanf("%c",&ch);
				if (ch=='.') map[i][j]=0;else
				{
					map[i][j]=ch-64;
					temp=ch-64;
					if (check[temp]==false)
					{
						check[temp]=true;
						countletter++;
						letterlist[countletter]=temp;
					}
				}
			}
			scanf("%c",&ch);
		}
		memset(check,false,sizeof(check));
}





int main()
{
	while (scanf("%d %d",&n,&m)!=-1)
	{
		scanf("%c",&ch);
		init();
		int temp;
		for (i=1;i<countletter;i++)
			for (j=i+1;j<=countletter;j++) if (letterlist[i]<letterlist[j]){temp=letterlist[i];letterlist[i]=letterlist[j];letterlist[j]=temp;}
		dfs(1);
	}
	return 0;
}

• 四个角坐标有可能判断错误 (460) xmuAres 2007-02-05 17:07:50
  • Re:四个角坐标有可能判断错误 (494) xmuAres 2007-02-05 17:11:52
  • Re:四个角坐标有可能判断错误 (530) fish_ball 2008-03-04 20:42:10