poj 3984 迷宮問題 bfs

      學會這道水題之後我懂得了不少哈，首先水題也能學到不少知識，尤其像我這樣剛入門的小菜鳥，能學到一些小技巧。

        然後就是可以從別人的代碼裡學到不一樣的思路和想法。

       這題就是求最短的路徑，首先想到就是用bfs，但是求到最短之後不知道怎麼輸出了咋辦？很著急有木有？？？

       基本的廣搜題已經做的挺熟練的，但是這個記錄路徑還是沒搞懂，大致的方向還是明白的，記錄，遞歸輸出。。。。

      然後我就找到了寫得不錯的代碼。。然後加上了我“本地化”處理，啊哈~~~~~~~·

 


 
#include<iostream>   
#include<stdio.h>   
#include<string.h>   
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<iostream>
#include<stdio.h>
#include<string.h>
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;
}