自动搬运

查看原文

来自洛谷，原作者为

	MY（一名蒟蒻） 你数据结构都用错了，怎么改都是没用的。

搬运于2025-08-24 22:18:32，当前版本为作者最后更新于2020-03-15 12:47:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题一看，妥妥的BFS嘛。

然鹅，窝秉承能深搜绝不广搜的想法，打了DFS（好久煤打忘得都差不多了）。

DFS想法：一条路走到黑，不行就返回。

蛋是，题目只需要窝们输出一条路径，所以窝们的book数组不需要取消标记（窝就是被这个坑了）。

注释详见代码。

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
//定义r,c(如题)，输出路径用的数组，为了省事写的next数组和做标记的book数组。
int r,c,ax[13000],ay[13000],next[4][2]={{0,1},{1,0},{0,-1},{-1,0}},book[130][90];
char farm[130][90];//地图
bool f=false;//判断是否输出过路径的变量
void dfs(int x,int y,int step)
{
	if(x < 1 || x > r || y < 1 || y > c) return ;//越界
	if(book[x][y]) return ;//来过
	if(farm[x][y] == '*') return ;//无法通行
	if(f) return ;//输出过路径
	if(x == r && y == c)//找到终点
	{
		for(int i=1;i<step;i++) printf("%d %d\n",ax[i],ay[i]);//输出，注意这里是i<step，因为窝们煤油把终点存进数组
		printf("%d %d",r,c);//所以需要单独输出
		f=true;//标记为以输出
		return ;
	}
	ax[step]=x;ay[step]=y;//将当前点坐标存入数组
	book[x][y]=1;//标记已走过
	for(int i=0;i<4;i++)
	{
		dfs(x+next[i][0],y+next[i][1],step+1);//继续搜索
		if(f) return ;//保险起见
	} 
	return ;
}
int main()
{
	scanf("%d %d",&r,&c);//输入
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) cin >> farm[i][j];
	dfs(1,1,1);//搜索
	return 0;
}

Thank you for your watching! 不介意的话，请您点个赞吧！