poj3984--BFS

//#define LOCAL
#include <stdio.h>
#include <string.h>

#define MAXN 5 + 10

struct node{
	int x;
	int y;
	int pre;
}queue[100];

int front, rear;
int graph[MAXN][MAXN];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void print(int i);
bool isIn(int x, int y);
void bfs();

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	int i, j;
	
	// 数据初始化
	 memset(queue, -1, sizeof(queue));
	 
	// 数据输入 
	for(i = 0; i < 5; i++)
	{
		for(j = 0; j < 5; j++)
		{
			scanf("%d", &graph[i][j]);
		}
	}
	
	// 算法主体
	bfs(); 

	 
	return 0;
}

void bfs()
{
	int a,b;
	front = 0;
	rear = 1;
	queue[front].x = 0;
	queue[front].y = 0;
	while(front < rear)
	{
		for(int i = 0; i < 4; i++)
		{
			a = dx[i] + queue[front].x;
			b = dy[i] + queue[front].y;
			if(!isIn(a, b) || graph[a][b])
				continue;
			else
			{
				graph[a][b] = 1;
				queue[rear].x = a;
				queue[rear].y = b;
				queue[rear].pre = front;
				rear++;
			}
			if(a == 4 && b == 4)
			{
				printf("(0, 0)\n");
				print(front);
				printf("(4, 4)\n");			
			}

		}
		front++;
	}	
}

bool isIn(int x, int y)
{
	if(x > 4 || x < 0 || y < 0 || y > 4)
		return false;
	return true; 
} 

void print(int i)
{
	if(queue[i].pre != -1)
	{
		print(queue[i].pre);
		printf("(%d, %d)\n", queue[i].x, queue[i].y);
	}
}

BFS的题目还是不是很擅长，就写这么个题目都花了好长时间，我还是太嫩了。。。