题解 - 走迷宫输出路径

0

CQS LV 8 @ 2025-3-24 16:47:14

#include <iostream>
using namespace std;

int a[20][20];
int n, m, qx, qy, zx, zy;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

int rec[410][2];
int cnt = 0;

void dfs(int x, int y, int k) {
    rec[k][0] = x;
    rec[k][1] = y;

    if (x == zx && y == zy) {
        cnt++;
        for (int i = 1; i < k; i++) {
            printf("(%d,%d)->", rec[i][0], rec[i][1]);
        }
        printf("(%d,%d)", rec[k][0],rec[k][1]);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 1) {
            a[nx][ny] = 0;
            dfs(nx, ny, k + 1);
            a[nx][ny] = 1;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> qx >> qy;
    cin >> zx >> zy;

    a[qx][qy] = 0;
    dfs(qx, qy, 1);

    if (cnt == 0) return -1;
}

0

Mandy LV 8 @ 2025-1-30 21:36:54

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
int a[N][N];
bool st[N][N];
vector<PII> rec;
int n, m;
int xStart, xEnd, yStart, yEnd;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int cnt;

void dfs(int x, int y, int k) {
    rec[k].first = x;
    rec[k].second = y;
    if (x == xEnd && y == yEnd) {
        cnt++;
        for (int i = 1; i < k; i++) 
            printf("(%d,%d)->", rec[i].first, rec[i].second);
        printf("(%d,%d)\n", rec[k].first, rec[k].second);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m){
        	if (!st[nx][ny] && a[nx][ny] == 1) {
            st[nx][ny] = true;
            dfs(nx, ny, k + 1);
            st[nx][ny] = false;
        	}
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    cin >> xStart >> yStart >> xEnd >> yEnd;
    st[xStart][yStart] = true;
    rec.resize(n * m + 1);
    dfs(xStart, yStart, 1);
    if (cnt == 0) cout << "-1" << endl;
    return 0;
}

0

yuri01 LV 9 @ 2025-1-5 16:45:39

// https://dashoj.com/p/84
// 1 可走 0 不可走
#include <bits/stdc++.h>

#define N 20
using namespace std;
typedef long long ll;

int n, m;
int ax, ay, bx, by;
int g[N][N];
bool gb[N][N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
vector<pair<int, int>> vp;
bool b = false;

void dfs(int x, int y) {
    if (x == bx && y == by) { // 到达终点
        b = true;
        for (int i = 0; i < vp.size() - 1; i++) {
            cout << '(' << vp[i].first << ',' << vp[i].second << ")->";
        }
        cout << '(' << x << ',' << y << ")" << endl;
        return;
    }
    for (int i = 0; i < 4; i++) { // 四个方向
        int vx = x + dx[i], vy = y + dy[i]; // 走方格
        if (vx >= 1 && vy >= 1 && vx <= n && vy <= m) { // 出界
            if (g[vx][vy] && gb[vx][vy]) { //
                gb[vx][vy] = false;
                vp.push_back({vx, vy});
                dfs(vx, vy);
                vp.pop_back();
                gb[vx][vy] = true;
            }
        }
    }
}

int main() {
    fill(&gb[0][0], &gb[0][0] + N * N, true);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    cin >> ax >> ay;
    cin >> bx >> by;
    gb[ax][ay] = false;
    vp.push_back({ax, ay});
    dfs(ax, ay);
    if (!b) {
        cout << -1 << endl;
    }
    return 0;
}

0

Well LV 8 @ 2024-5-24 17:06:56

n, m = map(int, input().split())
a = [[0] * (m + 2)]
a += [[0] + list(map(int, input().split())) + [0] for _ in range(n)]
a += [[0] * (m + 2)]
startx, starty = map(int, input().split())
endx, endy = map(int, input().split())

dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]
paths = []

def dfs(x, y, path):
    if (x, y) == (endx, endy):
        paths.append(path[:])
        return
    a[x][y] = 0
    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if a[nx][ny] == 1:
            path.append((nx, ny))
            dfs(nx, ny, path)
            path.pop()
    a[x][y] = 1

dfs(startx, starty, [(startx, starty)])

if paths:
    for path in paths:
        print("->".join(f"({x},{y})" for x, y in path))
else:
    print(-1)

0

Liopen LV 7 @ 2024-4-19 14:36:59

非递归方式！！利用栈实现，复杂度差不多，可以说基本一样，只是减少了递归方式的空间开销。

#include<cstdio>
#include<iostream>
using namespace std;

int posit[16][16];   //记录位置； 
int flag[16][16];	//记录是否走过 
int end1,end2;		//结束点 
int dy[4]={0,-1,0,1};    //方向 
int dx[4]={-1,0,1,0};
int n,m; 
int count=0; 
int mstate[300][2];    //数组模拟的栈     mstate[][0]存放y坐标，mstate[][1]存放x 
int top=1;				//栈顶指针，指向栈顶元素的下一个位置 

int whatp(int y,int x){        //当元素出站时会执行该函数，该函数为了计算回溯的方向，得出我下一次要从哪个方向开始 
	for(int i=0;i<4;++i){		//因为前面定义了dy，dx，顺序是左上右下，即为i=0，1，2，3
		if(y==dy[i]&&x==dx[i]) return i+1; 	//比如我是从上面回溯过来的，那么i就是1，于是我return i+1 也就是2，告知下一次要从（i=2）右开始找 
	}
	return 4;     //实际上不可能会有for循环外的情况，这里只是加上reutrn防止报错 
}
int main(){
	cin>>n>>m;
	int be1,be2;
	for(int i=1;i<=n;++i)						
	for(int j=1;j<=m;++j) cin>>posit[i][j];	
	char tmp[20];
	cin>>be1>>be2>>end1>>end2;
	mstate[0][0]=be1;       //栈底先加入第一个元素，也就是起始点 
	mstate[0][1]=be2;
	int nowx=be2,nowy=be1;    //表示当前走到了哪 
	int newx=be2,newy=be1;   	//前进的坐标 
	int oribx=0,oriby=0;    //从哪里回溯过来的坐标 
	int ifnext=0;         //是否有坐标可以让我前进 
	int p=0;			//从哪个方向开始 
	while(top>0){  
						//建议先从51行开始看 
		if(nowy==end1&&nowx==end2){
			for(int k=0;k<top-1;k++){           //这里就是走到终点时要打印路径了 
				sprintf(tmp,"(%d,%d)->",mstate[k][0],mstate[k][1]);
				cout<<tmp;
			}
			count++;     //找到一条路径就加一次 
			sprintf(tmp,"(%d,%d)",end1,end2);       
			cout<<tmp<<endl;
			top--;                              //我还要接着寻找有没有其他路径   所以回溯 
			nowy=mstate[top-1][0];nowx=mstate[top-1][1];     //这里的原理和69行一样 
			oriby=mstate[top][0];oribx=mstate[top][1];
			flag[oriby][oribx]=0;
			p=whatp(oriby-nowy,oribx-nowx);
		}
		else {
			ifnext=0;   
			for(int i=p;i<4;++i){    //比如我p=0，那么我就从左开始 左-》上-》右-》下  如果p=2，那么我就是从右开始 右-》下  
			newy=nowy+dy[i];newx=nowx+dx[i];     //计算出下一个想要走的坐标 
			if(newy<=n&&newy>0&&newx<=m&&newx>0&&flag[newy][newx]!=1&&posit[newy][newx]!=0){//判断下一个坐标能不能走 
				p=0;            //因为下个坐标是新的，那它一定是从 左上右下 开始走 
				nowy=newy;nowx=newx;     //更新位置 
				mstate[top][0]=newy;mstate[top][1]=newx;   //入栈 
				flag[newy][newx]=1;     //标记走过 
				top++;
				ifnext=1;            //这一次存在可以往下走的坐标 
				break;
			}
		}
		}			

		if(ifnext) continue;      //既然存在 可以往下走的坐标 那就不需要回溯了，跳过下面代码从头开始 
		
		top--;     	// 不存在可以往下走的坐标   那就要回溯了   栈顶指针向回走 
		nowy=mstate[top-1][0];nowx=mstate[top-1][1];         //回到上一个坐标，前面提到栈顶指针，指向栈顶元素的下一个位置  所以当前栈顶元素就top-1 
		oriby=mstate[top][0];oribx=mstate[top][1];     //top-1指向当前的栈顶元素，那么top指向的就是刚刚的栈顶元素 
		flag[oriby][oribx]=0;             //把刚才回溯过来的点标记为没走过 
		p=whatp(oriby-nowy,oribx-nowx);     //这里相当于计算出dy，dx，可以重写到函数定义处看看解释 
											//计算p值就是为了防止我下一次又走向刚刚回溯过来的点，陷入死循环 
	}
	if(count==0) cout<<-1;   //没有路径输出-1 
		
	return 0;
	
}

0

Dervish LV 4 @ 2024-4-18 21:50:00

#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define x first #define y second

const int N = 20; char g[N][N]; typedef pair<int, int> PII; vector<PII> res; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int n, m; bool st[N][N], flag; int x1, y1, x2, y2;

void dfs(int x, int y) { st[x][y] = true; if(x == x2 && y == y2) { flag = true; printf("(%d,%d)",x1,y1); for (int i = 1; i < res.size() - 1; i ++ ) printf("->(%d,%d)",res[i].x, res[i].y); printf("->(%d,%d)\n",x2,y2); } for (int i = 0; i < 4; i ++ ) { int a = x + dx[i], b = y + dy[i]; if(a<1 || a>n || b<1 || b>m || st[a][b] || g[a][b]=='0') continue; st[a][b] = true; res.push_back({a, b}); dfs(a, b); res.pop_back(); st[a][b] = false; } }

int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> g[i][j]; cin >> x1 >> y1; cin >> x2 >> y2;

res.push_back({x1, y1});
dfs(x1, y1);
if(!flag) cout << -1;
return 0;

}

0

Liopen LV 7 @ 2024-4-18 18:56:56

#include<cstdio>
#include<iostream>
using namespace std;

int posit[16][16];
int flag[16][16];
int end1,end2;
int dy[4]={0,-1,0,1};
int dx[4]={-1,0,1,0};
int n,m; 
int count=0; 

string dfs(int y,int x,string s){
	char tmp[12];
	if(y!=end1||x!=end2) {
		sprintf(tmp,"(%d,%d)->",y,x);
		s+=tmp;
	}
	else{
		sprintf(tmp,"(%d,%d)",y,x);
		cout<<s<<tmp<<endl;
		count++;
		return "";
	}
	
	int newy,newx;	
	
	for(int i=0;i<4;++i){
		newy=y+dy[i];
		newx=x+dx[i];
		if(newy>=1&&newy<=n&&newx>=1&&newx<=m&&posit[newy][newx]!=0&&flag[y][x]!=1){
			flag[y][x]=1;
			dfs(newy,newx,s); 
			flag[y][x]=0;
		}			
	}
	
	return s;
};

int main(){
	cin>>n>>m;
	int be1,be2;
	for(int i=1;i<=n;++i)						
	for(int j=1;j<=m;++j) cin>>posit[i][j];	
	
	cin>>be1>>be2>>end1>>end2;
	dfs(be1,be2,"");
	if(count==0) cout<<-1;
	return 0;
	
}

0

QiaoShen LV 6 @ 2024-4-9 22:22:25

//模板 #include <bits/stdc++.h> using namespace std; #define endl '\n' #define INF 0x3f3f3f3f3f3f3f3f

//移动向量 int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1};

//创建迷宫 int a[42][42];

//起点终点 pair<int , int> Start; pair<int , int> End;

//迷宫大小 int n,m;

//方案总数 int flag = 0;

//第一次 int diyici = 1;

//该点是否来过
bool coming[42][42];

//路线 vector<pair<int , int> > Path;

void dfs(pair<int , int> now) { if(now == End) { Path.push_back(End);

	for(int i = 0 ; i < Path.size() - 1 ; i++)
	{
		cout << "(" << Path[i].first + 1 << "," << Path[i].second + 1 << ")" << "->";
	}
	
	cout << "(" << Path[Path.size() - 1].first + 1<< "," << Path[Path.size() - 1].second + 1 << ")" << endl;
	
	flag = 1;
	
	Path.pop_back();
	coming[now.first][now.second] = 0;
}


for(int i = 0 ; i < 4 ; i++)
{
	Path.push_back(now);
	
	int nex = now.second + dx[i] , ney = now.first + dy[i];
	if(nex >= 0 && nex < m && ney >= 0 && ney < n /*位置可取*/ && coming[ney][nex] != 1 /*下一个位置未去过*/ && a[ney][nex] == 1 /*此路可通*/)
	{
		coming[now.first][now.second] = 1;
		coming[ney][nex] = 1;
		
		dfs({ney,nex});
		
		//回溯 
		coming[now.first][now.second] = 0;
		coming[ney][nex] = 0;
	}
	
	Path.pop_back();
}

return;

}

signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

memset(coming , 0 , sizeof(coming) );
memset(a , 0 , sizeof(a));

//初始化迷宫  
cin >> n >> m;
for(int i = 0 ; i < n ; i++)
{
	for(int j = 0 ; j < m ; j++)
	{
		cin >> a[i][j];
	}
}

//起点和终点  
int First,Second;

//(y,x)
//first -- y
//second -- x

//起点 
cin >> First >> Second;
Start.first = First - 1;
Start.second = Second - 1;

//终点 
cin >> First >> Second;
End.first = First - 1; // y
End.second = Second - 1; // x

/*
r(int i = 0 ; i < n ; i++)
{           1      =
	for(int j = 0 ; j < m ; j++)
	{           1      =
		cout << a[i][j];
	}
}

cout << "(" << Start.first << "," << Start.second << ")" ;
cout << "(" << End.first << "," << End.second << ")" ;

auto temp = make_pair(1,1);

if(Start == temp)
{
	cout << endl << "Right compare" << endl;
}
*/

dfs(Start);

if(flag == 0)
{
	cout << "-1";
}

return 0;

}

0

薛时锦 LV 7 @ 2024-4-8 20:49:13

DFS遍历每条路并回溯，用vector存放坐标

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> v;
const int N = 20;
int mp[N][N];
int vis[N][N];
int n,m;
int sx,sy;
int x2,y2;
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
int flag = 0;
void dfs(int x,int y){
    vis[x][y] = 1;
    if (x == x2 && y == y2) {
        flag = 1;
        printf("(%d,%d)",sx,sy);
        for (int i = 1; i < v.size() - 1; ++i){
            printf("->(%d,%d)",v[i].first,v[i].second);
        }
        printf("->(%d,%d)\n",x2,y2);
    }
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (vis[nx][ny]) continue;
        if (mp[nx][ny] == 0) continue;
        vis[nx][ny] = 1;
        v.push_back({nx,ny});
        dfs(nx,ny);
        v.pop_back();
        vis[nx][ny] = 0;
    }
    return;
}
int main(){
    scanf("%d %d",&n,&m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> mp[i][j];
        }
    }
    scanf("%d %d",&sx,&sy);
    scanf("%d %d",&x2,&y2);
    v.push_back({sx,sy});
    dfs(sx,sy);
    if(flag == 0) printf("-1\n");
    return 0;
}

0

Heng_Xin LV 7 @ 2024-4-5 22:25:16

回溯, ~~注:本题需要按照左上右下进行移动, 不然结果会被误判?~~ 😕(没错, 我就没看见这个qwq

#include <cstdio>
#include <vector>
#include <functional>
#include <utility>

using namespace std;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	vector<vector<char>> map(n, vector<char>(m));
	vector<vector<char>> ita(n, vector<char>(m));
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			int tmp;
			scanf("%d", &tmp);
			map[i][j] = tmp; // 1 可以走, 0 不可以走 
		}
	
	int s_x, s_y, e_x, e_y;
	scanf("%d %d", &s_y, &s_x);
	scanf("%d %d", &e_y, &e_x);
	--s_x, --s_y, --e_x, --e_y;
	
	bool tag = 1;
	
	int fx[4][2] = {
		{0, -1}, {-1, 0}, {0, 1}, {1, 0}
	};
	
	vector<pair<int, int>> lj; // 路径 (i, j)
	
	function<void(int, int)> dfs = [&](int i, int j) {
		if (i < 0 || j < 0 || i >= n || j >= m)
			return;
		
		if (ita[i][j] || !map[i][j])
			return; // 之前走过 || 不能走 
		
		if (i == e_y && j == e_x) {
			// 输出 
			for (int i = 0; i < lj.size(); ++i) {
				printf("(%d,%d)->", lj[i].first + 1, lj[i].second + 1);
			}
			printf("(%d,%d)\n", e_y + 1, e_x + 1);
			tag = 0;
			return;
		}
		
		ita[i][j] = 1;
		lj.push_back({i, j});
		for (auto& it : fx) {
			dfs(i + it[0], j + it[1]);
		}
		
		lj.pop_back();
		ita[i][j] = 0;
	};
	
	dfs(s_y, s_x);
	if (tag)
		printf("-1\n");
	
	return 0;
}

10 条题解

走迷宫输出路径

信息

工具

实用链接

QQ3号群

欢迎加入

QQ2号群

欢迎加入

QQ1号群

欢迎加入

在线询问

自动添加有问必答

10 条题解

走迷宫输出路径

信息

工具

实用链接

QQ3号群

欢迎加入

QQ2号群

欢迎加入

QQ1号群

欢迎加入

在线询问

自动添加有问必答

微信登录

账号密码登录