Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

代码在这儿...大牛们有心情可以指教一下嘛...只要给出一组让我出错的数据就行,谢谢了!

Posted by lcosvse at 2006-03-18 17:48:10 on Problem 1128
In Reply To:谁能出一组让我WA的数据啊~~~ Posted by:lcosvse at 2006-03-18 13:57:40
#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;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator