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

大牛帮我看下代码啊~!数据全过还是WA啊!!求救啊!!

Posted by chenzeyu at 2010-02-21 13:12:13 on Problem 3009
#include<iostream>

using namespace std;
int vis[22][22];
int route[22][22];
int possible;
const int MAXN = 2147483647;
int minstep;
void dfs(int x,int y,int r,int map[][22],int di)//di是4个方向DFS的编号
{
	if(r > minstep)	return;
	int temp[22][22];
	memcpy(temp,map,22*22*sizeof(int));
	if(di == 0)
	{
		dfs(x,y,r,temp,1);
		dfs(x,y,r,temp,2);
		dfs(x,y,r,temp,3);
		dfs(x,y,r,temp,4);
	}
	else if(di == 1)
	{
		if(temp[y+1][x] == -1||temp[y+1][x] == 1)
			return;
		route[y][x] = r;
		while(temp[y+1][x] == 0||temp[y+1][x] == 3)
		{
			if(temp[y+1][x] == 3)
			{
				possible = 1;
				if(r < route[y+1][x])
					route[y+1][x] = minstep = r;
				return;
			}
			y++;
			if(temp[y+1][x] == -1)
				return;
			if(temp[y+1][x] == 1)
			{
				temp[y+1][x] = 0;
				break;
			}
		}
		dfs(x,y,r+1,temp,1);
		dfs(x,y,r+1,temp,2);
		dfs(x,y,r+1,temp,3);
		dfs(x,y,r+1,temp,4);
	}
	else if(di == 2)
	{
		if(temp[y][x+1] == -1||temp[y][x+1] == 1)
			return;
		route[y][x] = r;
		while(temp[y][x+1] == 0||temp[y][x+1] == 3)
		{
			if(temp[y][x+1] == 3)
			{
				possible = 1;
				if(r < route[y][x+1])
					route[y][x+1] = minstep = r;
				return;
			}
			x++;
			if(temp[y][x+1] == -1)
				return;
			if(temp[y][x+1] == 1)
			{
				temp[y][x+1] = 0;
				break;
			}
		}
		dfs(x,y,r+1,temp,1);
		dfs(x,y,r+1,temp,2);
		dfs(x,y,r+1,temp,3);
		dfs(x,y,r+1,temp,4);
	} 
	else if(di == 3)
	{
		if(temp[y-1][x] == -1||temp[y-1][x] == 1)
			return;
		route[y][x] = r;
		while(temp[y-1][x] == 0)
		{
			if(temp[y-1][x] == 3)
			{
				possible = 1;
				if(r < route[y-1][x])
					route[y-1][x] = minstep = r;
				return;
			}
			y--;
			if(temp[y-1][x] == -1)
				return;
			if(temp[y-1][x] == 1)
			{
				temp[y-1][x] = 0;
				break;
			}
		}
		dfs(x,y,r+1,temp,1);
		dfs(x,y,r+1,temp,2);
		dfs(x,y,r+1,temp,3);
		dfs(x,y,r+1,temp,4);
	}
	else if(di == 4)
	{
		if(temp[y][x-1] == -1||temp[y][x-1] == 1)
			return;
		route[y][x] = r;
		while(temp[y][x-1] == 0||temp[y][x-1] == 3)
		{
			if(temp[y][x-1] == 3)
			{
				possible = 1;
				if(r < route[y][x-1])
					route[y][x-1] = minstep = r;
				return;
			}
			x--;
			if(temp[y][x-1] == -1)
				return;
			if(temp[y][x-1] == 1)
			{
				temp[y][x-1] = 0;
				break;
			}
		}
		dfs(x,y,r+1,temp,1);
		dfs(x,y,r+1,temp,2);
		dfs(x,y,r+1,temp,3);
		dfs(x,y,r+1,temp,4);
	} 
}

int main()
{
	int map[22][22];
	int w,h;
	int beginx,beginy,goalx,goaly;
	
	while(cin >> w >> h)
	{
		if(w == 0)break;
		memset(map,-1,sizeof(map));
		memset(vis,0,sizeof(vis));
		memset(route,0,sizeof(route));
		possible = 0;
		minstep = 10;
		for(int i = 1; i <= h;++i)
			for(int j = 1;j <= w;++j)
			{
				cin >> map[i][j];
				if(map[i][j] == 2)
				{
					beginx = j;
					beginy = i;
				}
				if(map[i][j] == 3)
				{
					goalx = j;
					goaly = i;
				}
			}
			route[goaly][goalx] = MAXN;
			route[beginy][beginx] = 1;
			map[beginy][beginx] = 0;
		dfs(beginx,beginy,1,map,0);
		if(possible)
			cout << minstep <<endl;
		else cout << -1 << endl;
	}
	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