[刷题笔记] ybt1255：迷宫问题

题目传送门

Solution

数据范围很小，一共才\(5\times5\)，所以乱搞做法很多

比如我一开始就先bfs单纯跑最短路，然后dfs找路径 但是忘回溯被嘲讽

其实可以边bfs边记录路径，因为bfs是按层数搜的，所以第一次到达终点的路径一定是最优的。

那么如何记录路径呢？我原来用pair，经教练指导发现可以用字符串记录，bfs 队列queue中传三个参数：x，y,和str（路径），具体实现见代码吧：

Code

std：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <string>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int mapp[N][N];
int vis[N][N];
struct Node
{
    int x,y;
    string str;
};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void bfs()
{
    queue <Node> q;
    q.push(Node{0,0});
    vis[0][0] = 0;
    while(!q.empty())
    {
        Node p = q.front();
        q.pop();
        if(p.x == 4 && p.y == 4) //注意我们并没有记录起点，需要单独输出一下起点
        {
            cout<<"(0, 0)\n";
            for(int i=0;i<p.str.length();i+=2)
            {
                cout<<"("<<p.str[i]<<", "<<p.str[i+1]<<")"<<endl;
            }
            return;
        }
        for(int i=0;i<4;i++)
        {
            int ax = p.x + dx[i];
            int ay = p.y + dy[i];
            if(ax>=0&&ax<5&&ay>=0&&ay<5&&vis[ax][ay] == INF &&!mapp[ax][ay])
            {
                string str_input = p.str+char(ax+'0')+char(ay+'0');
                vis[ax][ay] = vis[p.x][p.y] + 1;
                q.push(Node{ax,ay,str_input});
            }
        }

    }
}
int main()
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++) scanf("%d",&mapp[i][j]);
    }
    memset(vis,INF,sizeof(vis));
    bfs();
}

另外再附上我的暴力做法吧：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PAIR;
int mapp[N][N];
int vis[N][N];
int minn_step = 0;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
PAIR l[N];
void bfs()
{
	queue <PAIR> q;
	q.push(PAIR(0,0));
	vis[0][0] = 0;
	while(!q.empty())
	{
		PAIR p = q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int ax = p.first + dx[i];
			int ay = p.second + dy[i];
			if(ax>=0&&ax<5&&ay>=0&&ay<5&&vis[ax][ay] == INF&&!mapp[ax][ay] )
			{
				q.push(PAIR(ax,ay));
				vis[ax][ay] = vis[p.first][p.second] + 1;
			}
		}
	}
}
void dfs(int x,int y,int step,PAIR s[])
{
	if(x == 4 && y == 4)
	{
		if(step == minn_step) 
		{
			cout<<"(0, 0)\n";
			for(int i=0;i<step;i++) printf("(%d, %d)\n",s[i].first,s[i].second);
		}
		return;
	} 
	for(int i=0;i<4;i++)
	{
		int ax = x+dx[i];
		int ay = y + dy[i];
		if(ax>=0&&ax<5&&ay>=0&&ay<5&&vis[ax][ay] == INF &&!mapp[ax][ay])
		{
			s[step].first = ax;
			s[step].second = ay;
			vis[ax][ay] = 1;
			dfs(ax,ay,step+1,s);
			vis[ax][ay] = INF;
		}
	}
}
int main()
{
	memset(vis,INF,sizeof(vis));
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++) cin>>mapp[i][j];
	}
	bfs();
	minn_step = vis[4][4];
	memset(vis,INF,sizeof(vis));
	dfs(0,0,0,l);
}