BFS 经典题目详解

喜欢ヅ旅行 2023-07-03 07:10 24阅读 0赞

###  ###

*  【POJ】3984 迷宫问题（入门）
 *  【HDU】2612 Find a way（两次BFS）

# 【POJ】3984 迷宫问题（入门） #

> **原题链接：**[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984]

*  **思路：** 求最短路径一般就是广度优先搜索，定义结构体pre\[x\]\[y\]，表示该点的前一个元素，即保存路径。从左上角(0, 0)位置开始搜索，分别向上下左右搜索，已走过的点标记为1，未走过且可以走的点压入队列，最后当搜索到终点的时候，再把队列里的路径从头到尾一个个递归输出。

**C++ Code：**

#include <iostream>
    #include <queue>
    #define ll long long
    using namespace std;
    const int N=1e6+5;
    int cnt;
    int vis[10][10],maps[10][10];
    int dir_x[4]={ 0,0,1,-1};
    int dir_y[4]={ 1,-1,0,0};
    struct node{ 
        int x,y;
    };
    node pre[10][10];
    void out(node cur){ 
        if(cur.x==0 && cur.y==0){ 
            cout<<"("<<cur.x<<", "<<cur.y<<")"<<endl;
            return;
        }
        out(pre[cur.x][cur.y]);
        cout<<"("<<cur.x<<", "<<cur.y<<")"<<endl;
    }
    void bfs(){ 
        queue<node> q;
        node start;
        start.x=0,start.y=0;
        q.push(start);
        vis[0][0]=1;
        while(!q.empty()){ 
            node now = q.front();
            q.pop();
            if(now.x==4 && now.y==4){ 
                out(now);
                return;
            }
            for(int i=0;i<4;i++){ 
                node next;
                next.x=now.x+dir_x[i];
                next.y=now.y+dir_y[i];
                if(next.x>=0 && next.x<5 && next.y>=0 && next.y<5 && !vis[next.x][next.y] && !maps[next.x][next.y]){ 
                    vis[next.x][next.y]=1;
                    q.push(next);
                    pre[next.x][next.y]=now;
                }
            }
        }
    }
    int main(){ 
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++)
                cin>>maps[i][j];
        bfs();
    	return 0;
    }

**Java Code：**

import java.util.Scanner;
    class node{ 
    	int x,y,pre;
    	public node() { }
    	public node(int x,int y,int pre) { 
    		this.x=x;
    		this.y=y;
    		this.pre=pre;
    	}
    }
    public class Main { 
    	static int front=0,rear=1;
    	static int[][] dir = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    	static int[][] maps = new int[10][10];
    	static node[] q = new node[100];
    	static void print(int index) { 
    		if(q[index].pre!=-1) { 
    			print(q[index].pre);
    			System.out.println("("+q[index].x+", "+q[index].y+")");
    		}
    	}
    	static void bfs(int x,int y) { 
    		q[front]= new node(x,y,-1);
    		while(front<rear) { 
    			for(int i=0;i<4;i++) { 
    				for(int j=0;j<4;j++) { 
    					int xx=q[front].x+dir[i][0];
    					int yy=q[front].y+dir[i][1];
    					if(xx<0||xx>4||yy<0||yy>4||maps[xx][yy]!=0)
    						continue;
    					maps[xx][yy]=1;
    					q[rear] = new node(xx,yy,front);
    					if(xx==4&&yy==4)	print(rear);
    					rear++;
    				}
    			}
    			front++;
    		}
    	}
    	public static void main(String[] args) { 
    		Scanner cin = new Scanner(System.in);
    		for(int i=0;i<5;i++)
    			for(int j=0;j<5;j++)
    				maps[i][j]=cin.nextInt();
    		for(int i=0;i<100;i++)	//结构体要全部初始化，不然搜索时会报空指针异常
    			q[i]=new node();
    		System.out.println("(0, 0)");
    		bfs(0,0);
    	}
    }

# 【HDU】2612 Find a way（两次BFS） #

> **原题链接：**[http://acm.hdu.edu.cn/showproblem.php?pid=2612][http_acm.hdu.edu.cn_showproblem.php_pid_2612]

*  **题意：** @ 代表目的地，‘.’ 是可以走的路 ，‘\#’ 是不可以走的路，有多个目的地，Y和M两个人要到同一个目的地，问两个人到同一个目的地的最短路径和。
 *  **思路：** 两个人就跑两遍 BFS，每次 BFS 就记录到每个目的地所需的最短路径，最后比较每个目的地得出最小值。注意不能对每个目的地跑两遍，这样会TLE。还要考虑的一种特殊情况，就是当某个目的地不能到达时，就不考虑该点。

**C++ Code：**

#include <iostream>
    #include <cstring>
    #include <queue>
    #define inf 0x3f3f3f3f
    using namespace std;
    int dir[4][2]={ { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    int n,m,x1,y1,x2,y2,ex,ey;
    int vis[210][210],ans1[210][210],ans2[210][210];
    char maps[210][210];
    struct node{ 
        int x,y,step;
    };
    void bfs(int sx,int sy,char ch){ 
        memset(vis,0,sizeof(vis));
        queue<node> q;
        while(!q.empty())   q.pop();
        node start;
        start.x=sx, start.y=sy, start.step=0;
        vis[start.x][start.y]=1;
        q.push(start);
        while(!q.empty()){ 
            node now = q.front();
            q.pop();
            if(maps[now.x][now.y]=='@'){ 
                if(ch=='Y'){ 
                    ans1[now.x][now.y]=now.step;
                    vis[now.x][now.y]=1;
                }
                if(ch=='M'){ 
                    ans2[now.x][now.y]=now.step;
                    vis[now.x][now.y]=1;
                }
            }
            for(int i=0;i<4;i++){ 
                int xx=now.x+dir[i][0];
                int yy=now.y+dir[i][1];
                if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy] && maps[xx][yy]!='#'){ 
                    vis[xx][yy]=1;
                    node next;
                    next.x=xx, next.y=yy, next.step=now.step+1;
                    q.push(next);
                }
            }
        }
    }
    int main(){ 
        while(cin>>n>>m){ 
            for(int i=1;i<=n;i++){ 
                for(int j=1;j<=m;j++){ 
                    cin>>maps[i][j];
                    if(maps[i][j]=='Y')
                        x1=i,y1=j;
                    if(maps[i][j]=='M')
                        x2=i,y2=j;
                }
            }
            memset(ans1,0,sizeof(ans1));
            memset(ans2,0,sizeof(ans2));
            bfs(x1,y1,'Y');
            bfs(x2,y2,'M');
            int ans=inf;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    if(maps[i][j]=='@' && ans1[i][j] && ans2[i][j])
                        ans=min(ans,ans1[i][j]+ans2[i][j]);
            cout<<ans*11<<endl;
        }
        return 0;
    }

[http_poj.org_problem_id_3984]: http://poj.org/problem?id=3984
[http_acm.hdu.edu.cn_showproblem.php_pid_2612]: http://acm.hdu.edu.cn/showproblem.php?pid=2612