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 915507430 at 2014-09-03 10:39:03 on Problem 3984
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
	int x,y;
}node[30];
int father[30],map[5][5],vis[5][5];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
queue<Node>q;
void printf_1()
{
	int a[30];
	//printf("(0, 0)\n");
	int u=24;
	int j=0;
	while(1)
	{
		a[j++]=father[u];
		u=father[u];
		if(u==0)
			break;
	}
	//printf("(0, 0)\n");
	for(int i=j-1;i>=0;i--)
		printf("(%d, %d)\n",a[i]/5,a[i]%5);
	printf("(4, 4)\n");
}
void bfs(int x,int y)
{
	memset(vis,0,sizeof(vis));
	memset(father,-1,sizeof(father));
	vis[0][0]=1;
	Node now,next;
	now.x=0,now.y=0;
	//father[x*5+y]=0;
	q.push(now);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int dx=now.x+xx[i];
			int dy=now.y+yy[i];
			if(dx>=0&&dx<=4&&dy>=0&&dy<=4&&vis[dx][dy]==0&&map[dx][dy]==0)
			{
				vis[dx][dy]=1;
				father[dx*5+dy]=now.x*5+now.y;
				if(dx==4&&dy==4)
				{
					printf_1();
					return ;
				}
				next.x=dx;
				next.y=dy;
				q.push(next);
			}
		}
	}
}
int main ()
{
	for(int i=0;i<=4;i++)
		for(int j=0;j<=4;j++)
			scanf("%d",&map[i][j]);
	bfs(0,0);
	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