学会这道水题之后我懂得了不少哈，首先水题也能学到不少知识，尤其像我这样刚入门的小菜鸟，能学到一些小技巧。

然后就是可以从别人的代码里学到不一样的思路和想法。

这题就是求最短的路径，首先想到就是用bfs，但是求到最短之后不知道怎么输出了咋办？很着急有木有？？？

基本的广搜题已经做的挺熟练的，但是这个记录路径还是没搞懂，大致的方向还是明白的，记录，递归输出。。。。

然后我就找到了写得不错的代码。。然后加上了我“本地化”处理，啊哈~~~~~~~·

 


 
#include   
#include   
#include   
using namespace std;  
int map[5][5],vis[5][5],pre[100];  
struct loca{  
    int x;  
    int y;  
}list[50];  
  
int dir[8] = {0,1,0,-1,1,0,-1,0};  
  
int judge(int x,int y)  
{  
    if(x>=1&&x<5&&y>=0&&y<5&&!map[x][y])  
        return 1;  
    return 0;  
}  
  
void print(int x)   //递归输出哈，菜鸟学习了。。。   
{  
    int t;  
    t = pre[x];  
    if(t == 0)  
    {  
        printf("(0, 0)\n");  
        printf("(%d, %d)\n",list[x].x,list[x].y);  
        return ;  
    }  
    print(t);  
    printf("(%d, %d)\n",list[x].x,list[x].y);  
}  
  
void bfs()  
{  
    int i,head,tail;  
    int x,y,xx,yy;  
    memset(vis,0,sizeof(vis));  
    head = 0;  
    tail = 1;  
    list[0].x = 0;  
    list[0].y = 0;  
    pre[0] = -1;  
    while(head < tail)  
    {  
        x = list[head].x;  
        y = list[head].y;  
        if(x ==4 && y==4)  
        {  
            print(head);  
            return ;  
        }  
        for(i=0;i<8;i+=2)  
        {  
            xx = x + dir[i];  
            yy = y + dir[i+1];  
            if(!vis[xx][yy] && judge(xx,yy))  
            {  
                vis[xx][yy] = 1;  
                list[tail].x = xx;  
                list[tail].y = yy;  
                pre[tail] = head;  
                tail++;  
            }  
        }  
        head ++;  
    }  
    return ;  
}  
  
int main(void)  
{  
    int i,j;  
    for(i=0;i<5;i++)  
       for(j=0;j<5;j++)  
          scanf("%d",&map[i][j]);  
    bfs();  
    return 0;  
}  

#include
#include
#include
using namespace std;
int map[5][5],vis[5][5],pre[100];
struct loca{
	int x;
	int y;
}list[50];

int dir[8] = {0,1,0,-1,1,0,-1,0};

int judge(int x,int y)
{
	if(x>=1&&x<5&&y>=0&&y<5&&!map[x][y])
	    return 1;
    return 0;
}

void print(int x)   //递归输出哈，菜鸟学习了。。。
{
	int t;
	t = pre[x];
	if(t == 0)
	{
		printf("(0, 0)\n");
		printf("(%d, %d)\n",list[x].x,list[x].y);
		return ;
	}
	print(t);
	printf("(%d, %d)\n",list[x].x,list[x].y);
}

void bfs()
{
	int i,head,tail;
	int x,y,xx,yy;
	memset(vis,0,sizeof(vis));
	head = 0;
	tail = 1;
	list[0].x = 0;
	list[0].y = 0;
	pre[0] = -1;
	while(head < tail)
	{
		x = list[head].x;
		y = list[head].y;
		if(x ==4 && y==4)
	    {
	    	print(head);
	    	return ;
	    }
	    for(i=0;i<8;i+=2)
	    {
	    	xx = x + dir[i];
	    	yy = y + dir[i+1];
	    	if(!vis[xx][yy] && judge(xx,yy))
	    	{
	    		vis[xx][yy] = 1;
	    		list[tail].x = xx;
				list[tail].y = yy;
				pre[tail] = head;
				tail++;
			}
		}
		head ++;
	}
	return ;
}

int main(void)
{
	int i,j;
	for(i=0;i<5;i++)
	   for(j=0;j<5;j++)
	      scanf("%d",&map[i][j]);
    bfs();
    return 0;
}