首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题
  • 热度指数:192913 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

定义一个二维数组 N*M ,如 5 × 5 数组下所示:


int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};


它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。


数据范围: , 输入的内容只包含


输入描述:

输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。



输出描述:

左上角到右下角的最短路径,格式如样例所示。

示例1

输入

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
示例2

输入

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

输出

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

说明

注意:不能斜着走!!     

因为题目说了,只有一条有效路径,那么我们可以直接使用 dfs 搜索,而可以不用标准的 bfs 来找最短路径。

下面是不带剪枝策略的 dfs 回溯算法,非常直观,直接套用回溯算法模板即可。
代码清晰可读。

import sys


def print_result(path):
    for item in path:
        print('({},{})'.format(item[0], item[1]))


def min_path(maze, visited, path, m, n, i, j):
    if i >= m or j >= n or i < 0 or j < 0:
        return
    if visited[i][j]:
        return 
    if maze[i][j] == 1:
        return
    if i == m-1 and j == n-1 and maze[i][j] == 0:
        path.append((i, j))
        print_result(path)
        return

    path.append((i, j))
    visited[i][j] = True
    min_path(maze, visited, path, m, n, i+1, j)
    min_path(maze, visited, path, m, n, i-1, j) 
    min_path(maze, visited, path, m, n, i, j+1)
    min_path(maze, visited, path, m, n, i, j-1)
    path.pop()
    visited[i][j] = False


def get_input():
    m, n = list(map(int, input().strip().split()))

    maze = []
    for i in range(m):
        row = list(map(int, input().strip().split()))
        maze.append(row)

    return maze, m, n


if __name__ == '__main__':
    try:
        while True:
            maze, m, n = get_input()
            row = [False for _ in range(n)]
            visited = [row.copy() for _ in range(m)]    
            path = []
            min_path(maze, visited, path, m, n, 0, 0)
    except Exception:
        pass
编辑于 2021-05-07 09:16:22 回复(2)
#include <iostream>
#include <algorithm>

using namespace std;

int N,M;
vector<vector<int>> maze, mbest, mtmp;

//四个方向递归查找
void mazeTrack(int x, int y)
{
    maze[x][y] = 1;    //已走标记
    mtmp.push_back({x,y});
    
    if(x==N-1 && y==M-1)    //已走通
        if(mtmp.size()<mbest.size() || mbest.empty()) {
            mbest = mtmp;
            goto _END;    //到达终点不再继续该通道
        }
    
    if(x>0 && maze[x-1][y]==0)    //向上
        mazeTrack(x-1,y);
    if(x<N-1 && maze[x+1][y]==0)    //向下
        mazeTrack(x+1,y);
    if(y>0 && maze[x][y-1]==0)    //向左
        mazeTrack(x,y-1);
    if(y<M-1 && maze[x][y+1]==0)    //向右
        mazeTrack(x,y+1);

_END:
    //该条通道不可继续,回到上一层走上一个点的其他分支
    maze[x][y] = 0;    //恢复标记,因只有该点可走时才会走所以原本为0
    mtmp.pop_back();
}

int main()
{
    while(cin>>N>>M) {
        //输入存储
        maze = vector<vector<int>>(N, vector<int>(M,0));
            
        for(auto &i:maze)
            for(auto &j:i)
                cin>>j;
        
        mazeTrack(0, 0);
        for(auto x:mbest)
            cout<<"("<<x[0]<<","<<x[1]<<")"<<endl;
        
        maze.clear();
        mbest.clear();
        mtmp.clear();
    }
}

发表于 2019-08-10 12:29:19 回复(0)
try:
    while True:
        row,col = map(int,input().split())
        maze = []
        for i in range(row):
            maze.append(list(map(lambda x:-x,map(int,input().split()))))
        queue = [[0,0]]
        maze[0][0] = 1
        while queue:
            x,y = queue.pop(0)
            if x == row-1 and y == col-1:
                break
            if x+1 < row and maze[x+1][y] == 0:
                maze[x+1][y] = maze[x][y]+1
                queue.append([x+1,y])
            if y+1 < col and maze[x][y+1] == 0:
                maze[x][y+1] = maze[x][y]+1
                queue.append([x,y+1])
            if x-1 >= 0 and maze[x-1][y] == 0:
                maze[x-1][y] = maze[x][y]+1
                queue.append([x-1,y])
            if y-1 >= 0 and maze[x][y-1] == 0:
                maze[x][y-1] = maze[x][y]+1
                queue.append([x,y-1])
        result = [[row-1,col-1]]
        for i in range(maze[-1][-1]-1,0,-1):
            tempRow = result[0][0]
            tempCol = result[0][1]
            if tempRow-1>=0 and maze[tempRow-1][tempCol] == i:
                result.insert(0,[tempRow-1,tempCol])
            elif tempCol-1>=0 and maze[tempRow][tempCol-1] == i:
                result.insert(0,[tempRow,tempCol-1])
            elif tempRow+1<row and maze[tempRow+1][tempCol] == i:
                result.insert(0,[tempRow+1,tempCol])
            elif tempCol+1<col and maze[tempRow][tempCol+1] == i:
                result.insert(0,[tempRow,tempCol+1])
        for i in result:
            print('(%d,%d)'%(i[0],i[1]))
except Exception:
    pass
编辑于 2018-11-06 20:09:53 回复(1)
#coding=utf-8
while True:
    try:
        m,n=map(int,raw_input().split())
        a=[]
        for i in range(m):
            a.append(map(int,raw_input().split()))
        v=[[0 for i in range(n)]for j in range(m)]#visit
        d=[[0,1],[0,-1],[1,0],[-1,0]]#direction
        c=[1,1,3,0]#cost
        s=[]#step
        s.append([0,0])#begin at (0,0)
        v[0][0]=1#(0,0)has been visited
        i,j=s[-1]#init position
        k=0
        while k<4:#BFS
            x=i+d[k][0]
            y=j+d[k][1]
            if x>=0 and y>=0 and x<m and y<n and a[x][y]==0 and v[x][y]==0:
                s.append([x,y])
                v[x][y]=1
                i=x
                j=y
                k=-1
            if x==m-1 and y==n-1:
                break
            if k==3:
                s.pop()
            k+=1
        for k in s:
            print '(%d,%d)'%(k[0],k[1])
    except:
        break
编辑于 2017-08-19 22:18:14 回复(1)

C++解法一, DFS (回溯)

#include<bits/stdc++.h>
using namespace std;

int dirs[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int n, m, grid[10][10];
vector<pair<int, int>> bestPath, path;

void dfs(int x, int y) {
    grid[x][y] = 1;
    path.emplace_back(x, y);
    if (x == n - 1 && y == m - 1)   // 到达终点
        if (bestPath.empty() || path.size() < bestPath.size()) { bestPath = path; return; }

    for (auto &[dx, dy] : dirs) {
        int nx = x + dx, ny = y + dy;
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny]) continue;
        dfs(nx, ny);
    }
    path.pop_back();    // 还原状态
    grid[x][y] = 0;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];
    dfs(0, 0);
    for (auto &[x, y] : bestPath) {
        printf("(%d,%d)\n", x, y);
    }
    return 0;
}

C++解法二, BFS

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int dirs[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int grid[10][10], preX[10][10] = {}, preY[10][10] ={};

void dfs(int x, int y) {    // 打印路径
    if (x == 0 && y == 0) {
        cout << "(0,0)" << endl;
        return ;
    }
    dfs(preX[x][y], preY[x][y]);
    cout << '(' << x << ',' << y << ')' << endl;
}

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    queue<pair<int, int>> q;
    q.emplace(0, 0);    
    grid[0][0] = 1;
    bool flag = true;
    while (flag) {
        int size = q.size();
        while (size--) {
            auto [x, y] = q.front(); q.pop();
            if (x == n - 1 && y == m - 1) { flag = false; break; };    // 到达终点
            for (auto &[dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny]) continue;
                grid[nx][ny] = 1;    // 访问过不能再访问
                preX[nx][ny] = x, preY[nx][ny] = y;
                q.emplace(nx, ny);
            }
        }
    }
    dfs(n - 1, m - 1);
    return 0;
}
发表于 2022-08-17 10:10:51 回复(0)
#include<iostream>
#include<vector>
using namespace std;
bool func(vector<vector<int>>& mg, int x, int y,vector<pair<int, int>>& path){
    if(x == mg.size()-1 && y == mg[0].size()-1){//成功抵达
        path.push_back({x,y});
        return 1;
    }
    if(x<0 || x>=mg.size() || y<0 || y>=mg[0].size())
        return 0;
    if(mg[x][y] == 1)
        return 0;
    mg[x][y] = 1;//走过的,标为1
    if(func(mg, x+1, y, path) || func(mg, x-1, y, path)
       ||func(mg, x, y-1, path)||func(mg, x, y+1, path)){
        path.push_back({x,y});
        return 1;
    }
    return 0;
}
int main(){
    int x,y;
    while(cin >> x >> y){
        vector<vector<int>> mg(x,vector<int>(y,0));
        vector<pair<int, int>> path;//记录路径
        for(int i=0; i<x; i++){
            for(int j=0; j<y; j++){
                cin >> mg[i][j];
            }
        }
        func(mg,0,0,path);
        for(int i=path.size()-1; i>=0; i--){
            cout<<'('<<path[i].first<<','<<path[i].second<<')'<<endl;
        }
    }
    
    
    return 0;
}

发表于 2022-08-13 20:38:17 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool dfs(int dx, int dy, int n, int m, vector<vector<int>>& maze, vector<pair<int, int>>& ans) {
    /* 遇到墙或者出界 */
    if (dx < 0 || dy < 0 || dx == n && dy < m || dy == m && dx < n || maze[dx][dy] == 1)
        return false;
    /* 到达出口 */
    if (dx == n - 1 && dy == m - 1)
        return true;
    /* 标记当前位置 */
    maze[dx][dy] = 1;
    /* 向南走 */
    ans.push_back(make_pair(dx + 1, dy));
    if (dfs(dx + 1, dy, n, m, maze, ans))
        return true;
    ans.pop_back();
    /* 向东走 */
    ans.push_back(make_pair(dx, dy + 1));
    if (dfs(dx, dy + 1, n, m, maze, ans))
        return true;
    ans.pop_back();
    /* 向西走 */
    ans.push_back(make_pair(dx - 1, dy));
    if (dfs(dx - 1, dy, n, m, maze, ans))
        return true;
    ans.pop_back();
    /* 向北走 */
    ans.push_back(make_pair(dx, dy - 1));
    if (dfs(dx, dy - 1, n, m, maze, ans))
        return true;
    ans.pop_back();
    /* 都走不通则失败 */
    maze[dx][dy] = 0;
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> maze(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> maze[i][j];
    vector<pair<int, int>> ans;
    /* 从起点(0,0)开始 */
    dfs(0, 0, n, m, maze, ans);
    cout << "(0,0)" << endl;
    for (int i = 0; i < ans.size(); i++)
        cout << "(" << ans[i].first << "," << ans[i].second << ")" << endl;
    return 0;
}

发表于 2022-03-27 17:22:30 回复(0)
while True:
    try:
        m,n = map(int,input().split())
        matrix = []
        for i in range(m):
            d = list(map(int,input().split()))
            #print(c)
            matrix.append(d)
            
        def dfs(path):
            if path[-1] == [m-1,n-1]:
                return path
            r, c = path[-1]
            matrix[r][c] = 2
            directions = [[r+1,c],[r,c+1],[r-1,c],[r,c-1]]
            for i,j in directions:
                if 0<=i<m and 0<=j<n and matrix[i][j]==0:
                    final_path = dfs(path+[[i,j]])
                    if final_path[-1] == [m-1,n-1]:
                        return final_path
            return path#很重要,保证输出
        
                    
        path = dfs([[0,0]])
        for i in path:
            print('({},{})'.format(i[0],i[1]))      
    except:
        break
发表于 2022-01-10 12:16:36 回复(0)
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
var flag=true,m,n,arr=[],res
function findWay(i,j,direction,path){
    if(i==m-1 && j==n-1){
        for(let i in path){
            console.log('('+path[i][0]+','+path[i][1]+')')
        }
    }
    if(i+1<m && arr[i+1][j]==0 && direction[1]!=0){
        findWay(i+1,j,[0,1,1,1],path.concat([[i+1,j]]))
    }
    if(i-1>=0 && arr[i-1][j]==0 && direction[0]!=0){
        findWay(i-1,j,[1,0,1,1],path.concat([[i-1,j]]))
    }
    if(j+1<n && arr[i][j+1]==0 && direction[3]!=0){
        findWay(i,j+1,[1,1,0,1],path.concat([[i,j+1]]))
    }
    if(j-1>=0 && arr[i][j-1]==0 && direction[2]!=0){
        findWay(i,j-1,[1,1,1,0],path.concat([[i,j-1]]))
    }
}
rl.on('line', function (line) {
    const tokens = line.split(' ');
    if (tokens[tokens.length-1]=='') tokens.pop()
    if(flag){
        m=parseInt(tokens[0]),n=parseInt(tokens[1])
        flag=false
    }
    else{
        arr.push(tokens.map((value,index,arr)=>{
            return parseInt(value)
        }))
        if(arr.length==m){
            //console.log(arr)
            findWay(0,0,[0,1,0,1],[[0,0]])
            arr=[]
            flag=true
        }
    }
});
js递归
发表于 2021-09-27 19:12:36 回复(0)
感觉像小游戏一样,每到分岔路口存个档,撞墙了就回档,把错路全部标记为墙,档坏了回上一个档,直至终点。
题目确定仅有一条通路,也挺方便的
# include <iostream>
# include <vector>
using namespace std;

int main(){
    int m, n;
    vector<pair<int, int>> step = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    while(cin >> m >> n){
        vector<vector<int>> mapp(m+2, vector<int>(n+2, 1));  // 地图
        vector<pair<int, int>> path = {{1, 1}};  // 记录路径
        vector<pair<int, int>> save = {{1, 1}};  // 记录节点
        for(int i=1; i<=m; i++){
            for (int j=1; j<=n; j++) cin >> mapp[i][j];
        }
        mapp[1][1] = 1;
        while (path.back()!=make_pair(m, n)) {
            int wall = 0;
            pair<int, int> chc;
            for (int i=0; i<4; i++){
                int xn = path.back().first + step[i].first;
                int yn = path.back().second + step[i].second;
                if (mapp[xn][yn]==1) wall++;
                else {chc = make_pair(xn, yn);}
            }
            if (wall==4) {
                // 走过的地方全是墙,回退的时候会将死胡同标记为墙
                if (path.back() == save.back()) save.pop_back();
                while (path.back() != save.back()) path.pop_back();
            }else if (wall==3){
                path.push_back(chc);
                mapp[chc.first][chc.second] = 1;
            }else {
                save.push_back(path.back());
                path.push_back(chc);
                mapp[chc.first][chc.second] = 1;
            }
        }
        for (int i=0; i<path.size(); i++)
            cout << '(' << path[i].first-1 << ',' << path[i].second-1 << ')' << endl;
    }
    return 0;
}

发表于 2021-08-31 17:19:38 回复(0)
//回溯
import java.util.*;

public class Main{
    private static List<int[]> ans = new ArrayList<>();
    private static List<int[]> path = new ArrayList<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] maze = new int[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    maze[i][j] = sc.nextInt();
                }
            }
            //深度优先搜索
            dfs(maze, 0, 0);
            for(int[] arr : ans){
                System.out.println("("+arr[0]+","+arr[1]+")");
            }
            //清空路径path,结果集ans,实际ans指向新建对象,无需清空
            path.clear();ans.clear();
        }
    }
    
    private static void dfs(int[][] maze, int i, int j){
        //结束条件,一定要用路径新建集合,path最后会remove为空
        if(i==maze.length-1 && j==maze[0].length-1){
            path.add(new int[]{i, j});
            ans = new ArrayList<>(path);
            return;
        }
        //边界条件,剪枝
        if(i<0 || i>=maze.length || j<0 || j>=maze[0].length || maze[i][j]==1) return;
        
        //i,j加入集合,并且当前位置设置为障碍
        path.add(new int[]{i, j});
        maze[i][j]=1;
        //向四个方向递归
        dfs(maze, i+1, j);
        dfs(maze, i, j+1);
        dfs(maze, i-1, j);
        dfs(maze, i, j-1);
        //找到死胡同,回溯,撤销i,j选择,当前位置设置为可走
        path.remove(path.size()-1);
        maze[i][j]=0;
    }
}

发表于 2021-08-06 10:13:36 回复(2)
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
bfs搜索,然后打印路径即可--- 不想递归打印的,可以从从右下往左上搜索
/*
public class Main{

    static int n, N = 12, m;
    static int[][] g = new int[N][N];
    static boolean[][] st = new boolean[N][N];
    static int[][] dis = new int[][]{ {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            n = in.nextInt(); m = in.nextInt();
            for(int i = 0; i < n; i ++)
                for(int j = 0; j < m; j ++){
                    g[i][j] = in.nextInt();
                }

            for(int i = 0; i < n; i ++)
                Arrays.fill(st[i], false);
            bfs();
        }


    }

    static void bfs(){
        st[0][0] = true;
        Queue<Node> queue = new LinkedList<>();
        Node start = new Node(0, 0);
        queue.add(start);

        while(!queue.isEmpty()){
            Node t = queue.poll();
            int a = t.x, b = t.y;
            for(int[] d : dis){
                int x = a + d[0], y = d[1] + b;
                if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 1 || st[x][y]) continue;
                st[x][y] = true;
                Node tmp = new Node(x, y);
                tmp.next = t;
                if(x == n - 1 && y == m - 1){
                    //找到
                    print(tmp);
                    return;
                }
                queue.add(tmp);
            }

        }
    }

    static void print(Node root){
        if(root == null) return;
        print(root.next);
        System.out.println("(" + root.x + ","  + root.y + ")");
    }

    static class Node{
        int x, y;
        Node next;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

发表于 2021-08-03 14:01:25 回复(0)
从起点开始不断四个方向探索,直到走到出口,走的过程中我们借助栈记录走过路径的坐标,栈记录
坐标有两方面的作用,一方面是记录走过的路径,一方面方便走到死路时进行回溯找其他的通路。
#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef struct Position
{
    int row;
    int col;
}Pos;

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//栈创建

typedef Pos STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}Stack;

void StackInit(Stack* ps)
{
    assert(ps);

    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->a == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    ps->capacity = 4;
    ps->top = 0;//初始给0,top指向栈顶元素的下一个;
}

void StackDestory(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

//入栈
void StackPush(Stack* ps, STDataType x)
{
    assert(ps);

    if (ps->top == ps->capacity)
    {
        STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }

    ps->a[ps->top] = x;
    ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);//栈空了,直接终止报错

    ps->top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);//栈空了,直接终止报错

    return ps->a[ps->top - 1];
}

int StackSize(Stack* ps)
{
    assert(ps);

    return ps->top;
}

bool StackEmpty(Stack* ps)
{
    assert(ps);

    return ps->top == 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//迷宫主程序

Stack path;

//判断是否有通路
bool IsPass(int** Maze, int N, int M, Pos next)
{
    if (next.col >= 0 && next.col < M && next.row >= 0 && next.row < N && Maze[next.row][next.col] == 0)
        return true;
    else
        return false;
}

//判断是否有到终点的路
bool GetMazePath(int** Maze, int N, int M, Pos cur)
{
    StackPush(&path, cur);

    //判断是否到出口
    if (cur.col == M - 1 && cur.row == N - 1)
        return true;

    Pos next;
    //将走过的地方置2,防止重走
    Maze[cur.row][cur.col] = 2;
    
    //探测上下左右四个方向
    
    //上
    next = cur;
    next.row -= 1;
    if (IsPass(Maze, N, M, next))
    {
        //如果有通路将继续递归
        if (GetMazePath(Maze, N, M, next))
            return true;
    }

    //下
    next = cur;
    next.row += 1;
    if (IsPass(Maze, N, M, next))
    {
        if (GetMazePath(Maze, N, M, next))
            return true;
    }

    //左
    next = cur;
    next.col -= 1;
    if (IsPass(Maze, N, M, next))
    {
        if (GetMazePath(Maze, N, M, next))
            return true;
    }

    //右
    next = cur;
    next.col += 1;
    if (IsPass(Maze, N, M, next))
    {
        if (GetMazePath(Maze, N, M, next))
            return true;
    }

    //当走到思路,将走错的坐标删除
    StackPop(&path);
    return false;
}

//采用栈储存路径
//由于先进后出,栈顶为出口,栈底为入口,需要反过来
//所以再创建一个栈将数据倒过来再输出
void PrintPath(Stack path)
{
    Stack rPath;
    StackInit(&rPath);
    while (!StackEmpty(&path))
    {
        StackPush(&rPath, StackTop(&path));
        StackPop(&path);
    }

    while (!StackEmpty(&rPath))
    {
        Pos top = StackTop(&rPath);
        printf("(%d,%d)\n", top.row, top.col);
        StackPop(&rPath);
    }

    StackDestory(&rPath);
}

int main()
{
    int N = 0, M = 0;
    while (scanf("%d%d", &N, &M) != EOF)
    {
        //创建迷宫
        //先创建行坐标
        //由于是二位数组,先创建一个含有N个数组指针的指针数组,指针数组储存的是指针,所以指向这个指针数组的指针为二级指针
        //指针数组中每个指针都为数组指针,每个数组指针指向的数组为每一行
        int** Maze = (int**)malloc(sizeof(int*) * N);
        for (int i = 0; i < N; i++)
        {
            //Maze[i]就是int*,是一个指针,开辟的空间储存int
            Maze[i] = (int*)malloc(sizeof(int) * M);
        }

        //输入迷宫
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                scanf("%d", &Maze[i][j]);
            }
        }
        
        //初始化栈
        StackInit(&path);
        //定起点
        Pos entry = { 0,0 };

        if (GetMazePath(Maze, N, M, entry))
        {
            PrintPath(path);
        }
        else
        {
            printf("没有找到通路\n");
        }

        StackDestory(&path);

        for (int i = 0; i < N; i++)
        {
            free(Maze[i]);
        }
        free(Maze);
        Maze = NULL;
    }
    return 0;
}



发表于 2021-07-12 00:29:00 回复(0)
import sys

def print_result(path):
    for item in path:
        print('({},{})'.format(item[0], item[1]))

def min_path(maze, visited, path, m, n, i, j):
    if i >= m&nbs***bsp;j >= n&nbs***bsp;i < 0&nbs***bsp;j < 0:
        return
    if visited[i][j]:
        return 
    if maze[i][j] == 1:
        return
    if i == m-1 and j == n-1 and maze[i][j] == 0:
        path.append((i, j))
        print_result(path)
        return

    path.append((i, j))
    visited[i][j] = True
    min_path(maze, visited, path, m, n, i+1, j)
    min_path(maze, visited, path, m, n, i-1, j) 
    min_path(maze, visited, path, m, n, i, j+1)
    min_path(maze, visited, path, m, n, i, j-1)
    path.pop()
    visited[i][j] = False

def get_input():
    m, n = list(map(int, input().strip().split()))

    maze = []
    for i in range(m):
        row = list(map(int, input().strip().split()))
        maze.append(row)

    return maze, m, n

if __name__ == '__main__':
    try:
        while True:
            maze, m, n = get_input()
            row = [False for _ in range(n)]
            visited = [row.copy() for _ in range(m)]    
            path = []
            min_path(maze, visited, path, m, n, 0, 0)
    except Exception:
        pass

发表于 2021-07-11 11:25:09 回复(0)
#include<iostream>
#include<stdio.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main()
{
    int row,col;
    while(cin>>row>>col) {
        vector<vector<int>> dst(row,vector<int>(col,-1)); //dst[i][j]记录是从哪个格子到达的(i,j)
        vector<vector<int>> arr(row,vector<int>(col,0));
        for(int i=0;i<row;++i) {
            for(int j=0;j<col;++j)
                cin>>arr[i][j];
        }
        queue<pair<int,int>> q;
        dst[0][0]=0;
        q.push(pair<int,int>(0,0));
        int dx[4]={0,0,-1,1};
        int dy[4]={-1,1,0,0};
        bool flag=false;
        while(!q.empty()) {
            auto [x,y]=q.front(); q.pop();
            for(int i=0;i<4;++i) {
                int newx=x+dx[i];
                int newy=y+dy[i];
                if(newx>=0 && newx<row && newy>=0 && newy<col && arr[newx][newy]==0 && dst[newx][newy]==-1) {
                    dst[newx][newy]=x*100+y;
                    if(newx==row-1 && newy==col-1) {
                        flag=true;
                        break;
                    }
                    q.push(pair<int,int>(newx,newy));
                }
            }
            if(flag)
                break;
        }
        int from=dst[row-1][col-1];
        vector<string> res;
        while(from!=0) {
            int x=from/100;
            int y=from%100;
            res.push_back("("+to_string(x)+","+to_string(y)+")");
            from=dst[x][y];
        }
        cout<<"(0,0)"<<endl;
        for(int i=res.size()-1;i>=0;i--) {
            cout<<res[i]<<endl;
        }
        cout<<"("<<(row-1)<<","<<(col-1)<<")"<<endl;
    }
    return 0;
}

发表于 2021-06-27 19:52:04 回复(0)

鄙人认为本题出的一般,只有一条路径走得通为什么还要说求最短路径,而且只有一条路径走得通也让大家可以投机取巧,不用广度、深度优先搜索就能出结果(看已通过的代码);

附上本人的广度优先搜索代码:

def bfs(maze,x1,y1,x2,y2):
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    queue = [(x1,y1,-1)]
    path = []
    while queue:
        path.append(queue.pop(0))
        cur = (path[-1][0],path[-1][1])
        if cur == (x2,y2):
            res = [(path[-1][0],path[-1][1])]
            loc = path[-1][2]
            while loc != -1:
                res.append((path[loc][0],path[loc][1]))
                loc = path[loc][2]
            return res

        for d in directions:
            next_node = (cur[0]+d[0],cur[1]+d[1])
            if 0 <= next_node[0] < len(maze) and \
               0 <= next_node[1] < len(maze[0]) and \
               maze[next_node[0]][next_node[1]] == 0:
                maze[next_node[0]][next_node[1]] == 2
                queue.append((next_node[0],next_node[1],len(path)-1))
while True:
    try:
        m,n = list(map(int, input().split()))
        maze = []
        for i in range(m):
            maze.append(list(map(int, input().split())))
        res = bfs(maze, 0, 0, m-1, n-1)[::-1]
        for i in res:
            print('(%d,%d)'%(i[0],i[1]))
    except:
        break
发表于 2021-02-19 15:18:43 回复(0)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int row = in.nextInt();
            int col = in.nextInt();
            int[][] maze = new int[row][col];
            for (int i=0; i<row; i++) 
                for (int j=0; j<col; j++)
                    maze[i][j] = in.nextInt();
            recursion(maze, 0, 0, -1);
            ArrayList<Point> list = new ArrayList();
            int x = row - 1, y = col - 1;
            int n = maze[x][y];
            // 从右下角根据步数,开始搜索最优路径(唯一),循环放入list
            while (true) {
                // 因为从后面开始循环,所以每次放入第一位
                list.add(0,new Point(x, y));
                // 步数时负数,所以++
                n ++;
                // 为0,则表示到达左上角
                if (n == 0)
                    break;
                // 目的: 找出与n相同的步数
                if (x - 1 >= 0 && maze[x - 1][y] == n){
                    x -= 1;
                    continue;
                }
                if (x + 1 < row && maze[x + 1][y] == n){
                    x += 1;
                    continue;
                }
                if (y - 1 >= 0 && maze[x][y - 1] == n){
                    y -= 1;
                    continue;
                }
                if (y + 1 < col && maze[x][y + 1] == n){
                    y += 1;
                    continue;
                }
            }
            for (Point p : list)
                System.out.println("(" + p.r + "," + p.c + ")");
        }
    }
    
    // 深度优先搜索 (递归)
    // 思路 : 0 位可以走, 1 为墙, 递归时,传入走的步数 (这里从-1 开始递减)
    public static void recursion(int[][] maze, int r, int y, int i) {
        // 如果为墙, 或者当前位已经走过,且走的步数(负数) <= 当前位的步数 ,直接返回
        if (maze[r][y] == 1 || (maze[r][y] < 0 && maze[r][y] >= i)) 
            return;
        // 这里可以直接更新步数
        maze[r][y] = i;
        // 判断是否到达右下角
        if (r == maze.length - 1 && y == maze[0].length - 1)
            return;
        // 往上走
        if (r - 1 >= 0)
            recursion(maze, r - 1, y, i - 1);
        // 往下走
        if (r + 1 < maze.length)
            recursion(maze, r + 1, y, i - 1);
        // 往左走
        if (y - 1 >= 0)
            recursion(maze, r, y - 1, i - 1);
        // 往右走
        if (y + 1 < maze[0].length)
            recursion(maze, r, y + 1, i - 1);
    }
    
}
// 定义一个用来保存坐标的类
class Point {
    int r;
    int c;
    Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

发表于 2021-02-02 11:19:17 回复(0)
题目要求:路径唯一,则不是寻找最优路径,而是寻找唯一路径且数据规模不大,dfs递归+栈即可,递归地入栈从而得到所需答案。ps:走地图类题目常用技巧:1、使用step数组来决定方向和步数,2、在地图外围一圈防止越界,最后输出坐标均减一即可。
#include<iostream>
#include<stack>
using namespace std;

int step[4][2] = {
    0, 1,
    1, 0,
    0, -1,
    -1, 0
};

struct Pos {
    int x, y;
};

stack<Pos> s;
int map[15][15];

bool check(int x, int y, int n, int m) {
    if(map[x][y] == 1) return false;
    if(x == n && y == m) {
        s.push({x, y});
        return true;
    }
    for(int i = 0; i < 4; i++) {
        if(check(x + step[i][0], y + step[i][1], n, m)) {
            s.push({x, y});
            return true;
        }
    }
    return false;
}

int main() { 
    int n, m;
    while(cin >> n >> m) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                cin >> map[i][j];
        for(int i = 0; i <= n; i++) {
            map[i][0] = map[i][m + 1] = 1;
        }
        for(int i = 0; i <= m; i++) {
            map[0][i] = map[n + 1][i] = 1;
        }
        check(1, 1, n, m);
        while(!s.empty()) {
            cout << "(" << s.top().x - 1 << "," << s.top().y - 1  << ")" << endl;
            s.pop();
        }
    }
    return 0;
}


编辑于 2021-01-28 21:22:53 回复(0)
import java.util.*;

// HJ43
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();

            int[][] map = new int[n][m];

            for (int i = 0; i < n * m; i++) {
                int num = in.nextInt();
                map[i / m][i % m] = num;
            }
            Point start = new Point(0, 0, m), end = new Point(m - 1, n - 1, m);
            LinkedList<Point> result = compute(n, m, map, start, end);
            if (Objects.isNull(result)) {
                System.out.println("ERROR");
                continue;
            }
            result.forEach(System.out::println);

        }
    }


    private static LinkedList<Point> compute(int rowNum, int colNum, int[][] map, Point start, Point end) {
        // 构造邻接矩阵
        int pointNum = rowNum * colNum;
        int[][] lin = new int[pointNum][pointNum];
        Map<Integer, Point> repo = new HashMap<>(pointNum);
        repo.put(start.toIndex(), start);
        repo.put(end.toIndex(), end);
        for (int i = 0; i < pointNum; i++) {
            int x = i % colNum;
            int y = i / colNum;
            int pointType = map[y][x];

            repo.putIfAbsent(i, new Point(x, y, colNum));

            for (int j = 0; j < 9; j++) {

                int tx = x - 1 + (j % 3);
                int ty = y - 1 + (j / 3);
                if (tx < 0 || ty < 0 || tx >= colNum || ty >= rowNum) {
                    continue;
                }
                int targetIndex = toIndex(tx, ty, colNum);
                if (i == targetIndex || lin[i][targetIndex] > 0) {
                    continue;
                }
                if (j == 0 || j == 2 || j == 4 || j == 6 || j == 8) {
                    continue;
                }
                switch (pointType) {
                    case 1:
                        lin[i][targetIndex] = 1;
                        lin[targetIndex][i] = 1;
                        break;
                    case 0:
                        if (map[ty][tx] == 1) {
                            lin[i][targetIndex] = 1;
                            lin[targetIndex][i] = 1;
                        } else {
                            lin[i][targetIndex] = 2;
                            lin[targetIndex][i] = 2;
                        }
                        break;
                }
            }
        }

        // 查询数量

        return computeAvailable(lin, repo, start, end, rowNum, colNum);


    }

    private static LinkedList<Point> computeAvailable(int[][] lin, Map<Integer, Point> repo, Point p1, Point p2, int rowNum, int colNum) {
        p1.passed = true;
        if (lin[p1.toIndex()][p2.toIndex()] == 2) {
            p1.passed = false;
            return new LinkedList<>(Arrays.asList(p1, p2));
        }

        boolean available = false;
        LinkedList<Point> minSubList = new LinkedList<>();
        for (int i = 0; i < 9; i++) {

            int tx = p1.x - 1 + (i % 3);
            int ty = p1.y - 1 + (i / 3);
            if (tx < 0 || ty < 0 || tx >= colNum || ty >= rowNum) {
                continue;
            }
            int targetIndex = toIndex(tx, ty, colNum);
            Point targetPoint = repo.get(targetIndex);
            if (!targetPoint.passed && lin[p1.toIndex()][targetPoint.toIndex()] == 2) {
                LinkedList<Point> subList = computeAvailable(lin, repo, targetPoint, p2, rowNum, colNum);
                if (Objects.nonNull(subList) && subList.size() < (minSubList.isEmpty() ? repo.size() : minSubList.size())) {
                    minSubList = subList;
                    available = true;
                }
            }
        }
        p1.passed = false;
        if (available) {
            minSubList.addFirst(p1);
            return minSubList;
        }
        return null;
    }

    private static int toIndex(int x, int y, int colNum) {
        return y * colNum + x;
    }

    private static class Point {
        final int x;
        final int y;
        final int colNum;
        boolean passed = false;

        public Point(int x, int y, int colNum) {
            this.x = x;
            this.y = y;
            this.colNum = colNum;
        }


        public int toIndex() {
            return y * colNum + x;
        }

        @Override
        public String toString() {
            return "(" + y +
                    "," + x +
                    ')'
                    ;
        }
    }
}

发表于 2020-11-11 03:45:51 回复(0)
def trace(start, end, maps):
    # 获取坐标
    m, n = len(maps), len(maps[0])
    x, y = start[0], start[1]
    # 判断能否走
    if x < 0&nbs***bsp;y < 0&nbs***bsp;x > m - 1&nbs***bsp;y > n - 1: return
    if maps[x][y] == 1: return
    # 走过的路改为 1,添加到路径
    maps[x][y] = 1
    stack.append(start)
    # 判断是否到达终点
    if start == end:
        if best_path == []&nbs***bsp;len(stack) < len(best_path):
            best_path.clear()
            for p in stack:
                best_path.append(p)
    # 这里防止到达终点后继续走下一步,不加也行,只是迭代步数更多
            stack.pop()
            maps[x][y] = 0
            return
    # 向四个方向走
    trace([x - 1, y], end, maps)
    trace([x + 1, y], end, maps)
    trace([x, y - 1], end, maps)
    trace([x, y + 1], end, maps)
    # 还原,删除路径
    stack.pop()
    maps[x][y] = 0


while True:
    try:
        MAP = []
        stack = []
        best_path = []
        M, N = map(int, input().split())
        for point in range(M):
            MAP.append(list(map(int, input().split())))
        trace([0, 0], [M - 1, N - 1], MAP)
        for point in best_path:
            print('(%d,%d)' % (point[0], point[1]))
    except:
        break

编辑于 2020-09-17 17:56:55 回复(0)