POJ 3626 Mud Puddles練習BFS幅優先検索

http://poj.org/problem?id=3626
 
Mud Puddles
Time Limit: 1000 MS
 
メモリLimit: 65536 K
Description
Farmer John is leaving his house promputlyt at 6 AM for his daily miking of Bessie.However，the previous evining saw a heavy ran，and the fields are quite muddy.FJ starts the point(0，0)in the the the the the the the the the the the the the the the the the waadcooraturis。 Y)（-500≦ X ≤500;-500≦ Y ≤500).He can see all N （1≦ N ≤10,000)putddles of mutd、located at points(Ai、 Bi)（-500≦ Ai ≤500;-500≦ Bi ≦500）on the field.Each puddle occupies only the point it is on.
Having just bought new bowbots、Farmer Joe absoutely dot t want to dirty them by stepping in puddle、but he also want s to get Bessie as quicklyas possiblble.Hes already late aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaager coordination、what is the shot distance he must travel to reach Bessie and keep his boots clean？The e e will always be a path without mut that Farmer John can tare to reach Bessie.
Input
*Line 1:Three space-separate integers: X， Y，and N.*Lines 2.N+1:Line i＋1 contains two space-separated integers: Ai and Bi
Output
*Line 1：The minimum distance that Farmer John has to travel to reach Bessie without stepping in mut.
Sample Input

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

Sample Output

11

/* Author : yan
 * Question : POJ 3626 Mud Puddles
 * Data && Time : Saturday, January 08 2011 11:39 PM
 * Compiler : gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
*/
#include<stdio.h>
#define bool _Bool
#define false 0
#define true 1
#define MAX 1003
typedef struct _node
{
	int x,y,step;
};
struct _node queue[MAX*MAX];
bool map[MAX][MAX];
bool visited[MAX][MAX];
int head,rear;
int X,Y;

int bfs()
{
	struct _node node;
	struct _node cache;
	node.x=500;
	node.y=500;
	node.step=0;
	queue[rear++]=node;
	while(head!=rear)
	{
		cache=queue[head++];
		//printf("%d %d/n",cache.x,cache.y);
		if(cache.x==X && cache.y==Y) return cache.step;
		if(cache.x>0)
		{
			node=cache,node.step++;
			node.x--;
			if(visited[cache.x-1][cache.y]==false && map[cache.x-1][cache.y]==false)
				queue[rear++]=node,visited[node.x][node.y]=true;
		}
		if(cache.y>0)
		{
			node=cache,node.step++;
			node.y--;
			if(visited[cache.x][cache.y-1]==false && map[cache.x][cache.y-1]==false)
				queue[rear++]=node,visited[node.x][node.y]=true;
		}
		if(cache.x<1000)
		{
			node=cache,node.step++;
			node.x++;
			if(visited[cache.x+1][cache.y]==false && map[cache.x+1][cache.y]==false)
				queue[rear++]=node,visited[node.x][node.y]=true;
		}
		if(cache.y<1000)
		{
			node=cache,node.step++;
			node.y++;
			if(visited[cache.x][cache.y+1]==false && map[cache.x][cache.y+1]==false)
				queue[rear++]=node,visited[node.x][node.y]=true;
		}
	}
	return 0;

}
int main()
{
	freopen("input","r",stdin);
	int n;
	int x,y;
	int i;
	scanf("%d %d %d",&X,&Y,&n);
	X+=500;
	Y+=500;
	for(i=0;i<n;i++)
	{
		scanf("%d %d",&x,&y);
		map[x+500][y+500]=true;
	}
	printf("%d",bfs());
	return 0;
}