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

第一次dfs过了。。。哈哈。。。留念

Posted by huxinjie at 2009-08-15 15:24:38 on Problem 1154
#include <iostream>
using namespace std;
char state[25][25];
int mmax;
bool flag[30];
int dfs (int x,int y,int r,int s,int count)
{
	if(x+1<r&&flag[state[x+1][y]-'A']==0)
	{
		flag[state[x+1][y]-'A']=1;
		count++;
		dfs(x+1,y,r,s,count);
		count--;
		flag[state[x+1][y]-'A']=0;
	}
	if(y+1<s&&flag[state[x][y+1]-'A']==0)
	{
		flag[state[x][y+1]-'A']=1;
		count++;
		dfs(x,y+1,r,s,count);
		count--;
		flag[state[x][y+1]-'A']=0;
	}
	if(x-1>=0&&flag[state[x-1][y]-'A']==0)
	{
		flag[state[x-1][y]-'A']=1;
		count++;
		dfs(x-1,y,r,s,count);
		count--;
		flag[state[x-1][y]-'A']=0;
	}
	if(y-1>=0&&flag[state[x][y-1]-'A']==0)
	{
		flag[state[x][y-1]-'A']=1;
		count++;
		dfs(x,y-1,r,s,count);
		count--;
		flag[state[x][y-1]-'A']=0;
	}
	if(count>mmax)
	{
		mmax=count;
		return 0;
	}
}
int main ()
{
	int r,s,i,j;
	scanf("%d%d",&r,&s);
	getchar();
	mmax=0;
	for(i=0;i<30;i++)flag[i]=0;
	for(i=0;i<r;i++)
	{
		for(j=0;j<s;j++)
			scanf("%c",&state[i][j]);
		getchar();
	}
	flag[state[0][0]-'A']=1;
	dfs(0,0,r,s,1);
	printf("%d\n",mmax);
	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