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 hustpd2 at 2009-08-20 17:20:48 on Problem 3009
#include<stdio.h>
#include<string.h>
#define MAX 100
int w,h;
int start_x,start_y;
int flag[MAX][MAX];
int min,step;
void dfs(int x,int y,int step)
{
	if(step>10) return;
	for(int i=x+1;i<h;i++)
	{
		if(i==x+1&&flag[i][y]==1) break;
		if(flag[i][y]==3){if(min>step) min=step;return;}
		if(flag[i][y]==1&&step<min){flag[i][y]=0;dfs(i-1,y,step+1);flag[i][y]=1;break;}
	}
	for(int i=x-1;i>=0;i--)
	{
		if(i==x-1&&flag[i][y]==1) break;
		if(flag[i][y]==3){if(min>step);min=step;return;}
		if(flag[i][y]==1&&step<min){flag[i][y]=0;dfs(i+1,y,step+1);flag[i][y]=1;break;}
	}
	for(int i=y+1;i<w;i++)
	{
		if(i==y+1&&flag[x][i]==1) break;
		if(flag[x][i]==3){if(min>step) min=step;return;}
		if(flag[x][i]==1&&step<min){flag[x][i]=0;dfs(x,i-1,step+1);flag[x][i]=1;break;}
	}
	for(int i=y-1;i>=0;i--)
	{
		if(i==y-1&&flag[x][i]==1) break;
		if(flag[x][i]==3&&step<min){if(min>step) min=step;return;}
		if(flag[x][i]==1&&step<min){flag[x][i]=0;dfs(x,i+1,step+1);flag[x][i]=1;break;}
	}
	return;
}


int main()
{
	while(scanf("%d %d",&w,&h)!=EOF)
	{
		if(w==0&&h==0) break;
		for(int i=0;i<h;i++)
		{
			 for(int j=0;j<w;j++)
			 {
					scanf("%d",&flag[i][j]);
					if(flag[i][j]==2) 
					{
						start_x=i;
						start_y=j;
						flag[i][j]=0;
					}
			 }
		}
		step=1;
		min=10000;
		dfs(start_x,start_y,step);
		if(min==10000) printf("-1\n");
		else printf("%d\n",min); 
	}
	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