首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题
  • 热度指数:202121 时间限制: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)

说明

注意:不能斜着走!!     
#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)
import java.util.*;
public class Main{
    //存储所有的路径和路径长度
    static Map<LinkedList<String>, Integer> res = new HashMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[][] arr = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            res.clear();
            LinkedList<String> trace = new LinkedList<>();
            int x = 0;
            int y = 0;
            dfs(arr, 0, 0, 1, trace);
            int min = Integer.MAX_VALUE;
            LinkedList<String> minTrace = new LinkedList<>();
            for(Map.Entry<LinkedList<String>, Integer> t : res.entrySet()){
                if(t.getValue() < min){
                    min = t.getValue();
                    minTrace = t.getKey();
                }
            }
            for(int i=0; i<minTrace.size(); i++){
                System.out.println(minTrace.get(i));
            }

        }
    }
    public static void dfs(int[][] arr, int x, int y, int cnt, LinkedList<String> trace){
        int m = arr.length;
        int n = arr[0].length;
        if(x == m-1 && y == n-1){
            trace.add("(" + x + "," + y +")");
            res.put(new LinkedList<>(trace), cnt);
            return;
        }
        if(x >= m || y >= n || arr[x][y] == 1 ){
            return;
        }
        //添加当前节点为trace
        trace.add("(" + x + "," + y +")");
        dfs(arr, x+1, y,cnt+1, trace);
        dfs(arr, x, y+1, cnt+1, trace);
        trace.removeLast();
    }
}





发表于 2020-08-23 21:56:54 回复(0)
import java.util.Scanner;
public class Main{
    private static int a,b;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            a = sc.nextInt();
            b = sc.nextInt();
            int[][] matrix = new int[a][b];
            for(int i=0;i<a;i++){
                for(int j=0;j<b;j++){
                    matrix[i][j]=sc.nextInt();
                }
            }
            getRoute(matrix,0,0);
        }
        sc.close();
    }
    
    public static boolean getRoute(int[][] matrix,int i,int j){
         if(i==(a-1) && j==(b-1)){
             System.out.println( "(" + i + "," + j +")" );
             return true;
         }
         if(matrix[i][j]==0){
                 matrix[i][j]=1;
                 System.out.println( "(" + i + "," + j +")" );
                 if(i<a && j<(b-1) && getRoute(matrix,i,j+1))
                     return true;
                 else if(i<(a-1) && j<b && getRoute(matrix,i+1,j))
                     return true;
                 else return false;
         }else{
             return false;
         }
    }
}
发表于 2020-08-05 11:40:17 回复(0)
Java BFS, 妈蛋中间出了些小bug找了我半个小时。。。。
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int row = sc.nextInt();
            int col = sc.nextInt();
            int[][] maze = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    maze[i][j] = sc.nextInt();
                }
            }
            Main main = new Main();
            bfs(maze);
        }
        sc.close();
    }
    public static void bfs(int[][] maze) {
        Queue<Point> q = new LinkedList<>();
        List<List<Point>> map = new ArrayList<>();
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        for (int i = 0; i < maze.length; i++) {
            Arrays.fill(visited[i], Boolean.FALSE);
            map.add(new ArrayList<Point>());
            for (int j = 0; j < maze[0].length; j++) {
                map.get(i).add(new Point(i, j));
            }
        }
        visited[0][0] = true;
        q.offer(map.get(0).get(0));
        loop: while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Point curr = q.poll();
                for (int[] dir : dirs) {
                    int xx = curr.getX() + dir[0], yy = curr.getY() + dir[1];
                    //迷宫范围内   可以通过   之前没走过
                    if (xx >= 0 && xx < maze.length && yy >= 0 && yy < maze[0].length && maze[xx][yy] == 0 && !visited[xx][yy]) {
                        visited[xx][yy] = true;
                        Point p = map.get(xx).get(yy);
                        p.setPrev(curr);
                        q.offer(p);
                        if (xx == maze.length - 1 && yy == maze[0].length - 1) {
                            break loop;
                        }
                    }
                }
            }
        }
        //从终点反推找回起点
        List<Point> path = new ArrayList<>();
        Point curr = map.get(maze.length - 1).get(maze[0].length - 1);
        while (curr != null) {
            path.add(curr);
            curr = curr.getPrev();
        }
        
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.println("(" + path.get(i).getX() + "," + path.get(i).getY() + ")");
        }
    }

}
class Point {
    private int x, y, len;
    private Point prev;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        prev = null;
    }
    public int getX(){
        return x;
    }
    public int getY(){
        return y;
    }
    public void setPrev(Point p) {
        prev = p;
    }
    public Point getPrev() {
        return prev;
    }
}

发表于 2020-07-19 16:51:09 回复(0)

深度优先遍历搜索。
从(0,0)开始整个矩阵矩阵,只能向上向下,向左向右走,且前方没有障碍物并且没有走过。遍历过程需要记录下来当前点是从哪个点(如果为点(i,j)存储对于id: i*m+j)走过来的。当遍历到(n,m)时,可以得到一条最短路径。然后从(n,m)倒序恢复整条路径。

import java.util.*;
public class Main {
    static int[] dx, dy;
    static int[][] bfs(int[][] grid, int n, int m) {
        //id : x*m + y
        int[][] ans = new int[n][m];
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        while(!q.isEmpty()) {
                int cur = q.poll();
                int x = cur / m, y = cur % m;
                //System.out.println(x+","+y);
                for(int j=0; j < 4; j++) {
                    int xx = dx[j] + x, yy = dy[j] + y;
                    if(xx>= 0 && xx<n && yy >=0 && yy < m && grid[xx][yy] == 0) {
                        grid[xx][yy] = 2;
                        q.offer(xx*m+yy);
                        ans[xx][yy] = cur;
                    }
                }
        }
        //System.out.println(Arrays.deepToString(ans));
        return ans;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        dx = new int[] {0, 1, 0, -1};
        dy = new int[] {1, 0, -1, 0};
        while(sc.hasNext()){
            int n =sc.nextInt(), m = sc.nextInt();
            int[][] grid = new int[n][m];
            for(int i=0; i < n; i++)
                for(int j=0; j < m; j++)
                    grid[i][j] = sc.nextInt();
            int[][] path = bfs(grid, n, m);
            List<int[]> res = new ArrayList<>();
            res.add(new int[] {n-1, m-1});
            int x = n-1, y = m-1;
            while(!(x == 0 && y == 0)) {
                int t = path[x][y];
                x = t / m; y = t % m;
                res.add(new int[] {x, y});
            }
            for(int i=res.size()-1; i >= 0; i--) {
                System.out.println("(" + res.get(i)[0] +"," + res.get(i)[1]+")");
            }
        }
    }
}
发表于 2020-07-09 12:30:23 回复(0)
本题可用回溯法求解 具体步骤为:
1. 首先将当前点加入路径,并设置为已走
2. 判断当前点是否为出口,是则输出路径,保存结果;跳转到4
3. 依次判断当前点的上、下、左、右四个点是否可走,如果可走则递归走该点
4. 当前点推出路径,设置为可走
#include <iostream>
#include <vector>
using namespace std;
int m, n;//分别代表行和列
vector<vector<int>> maze;//迷宫矩阵
vector<vector<int>> path_temp;//存储当前路径,第一维表示位置
vector<vector<int>> path_best;//存储最佳路径
void MazeTrack(int i, int j){
    maze[i][j] = 1;//标记当前节点已走,不可再走
    path_temp.push_back({i, j});//将当前节点加入到路径中
    if(i == m - 1 && j == n - 1){//判断是否到达终点
        if(path_best.empty() || path_temp.size() < path_best.size()){
            path_best = path_temp;
        }
    }
    if(i - 1 >= 0 && maze[i - 1][j] == 0){//探索向上走是否可行
        MazeTrack(i - 1, j);
    }
    if(i + 1 < m && maze[i + 1][j] == 0){//探索向下走是否可行
        MazeTrack(i + 1, j);
    }
    if(j - 1 >= 0 && maze[i][j - 1] == 0){//探索向左走是否可行
        MazeTrack(i, j - 1);
    }
    if(j + 1 < n && maze[i][j + 1] == 0){//探索向右走是否可行
        MazeTrack(i, j + 1);
    }
    maze[i][j] = 0;//恢复现场,设为未走
    path_temp.pop_back();
}
int main(){
    while(cin >> m >> n){
        maze = vector<vector<int>>(m, vector<int>(n, 0));
        path_temp.clear();
        path_best.clear();
        for(auto& i : maze){
            for(auto& j : i){
                cin >> j;
            }
        }
        MazeTrack(0, 0);//回溯寻找迷宫的最短路径
        for(auto& i : path_best){
            cout << '(' << i[0] << ',' << i[1] << ')' << endl;//输出通路
        }
    }
    return 0;
}
另一种方式遍历(简单一点):
#include <iostream>
#include <vector>
using namespace std;
int m, n;//分别代表行和列
vector<vector<int>> maze;//迷宫矩阵
vector<vector<int>> path_temp;//存储当前路径,第一维表示位置
vector<vector<int>> path_best;//存储最佳路径
int _nextPosition[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void MazeTrack(int x, int y){
    maze[x][y] = 1;//标记当前节点已走,不可再走
    path_temp.push_back({x, y});//将当前节点加入到路径中
    if(x == m - 1 && y == n - 1){//判断是否到达终点
        if(path_best.empty() || path_temp.size() < path_best.size()){//最小路径
            path_best = path_temp;
            return;
        }
    }
    for(int k = 0; k < 4; ++k){
        int nx = x + _nextPosition[k][0];
        int ny = y + _nextPosition[k][1];
        //如果位置越界或者是1,则跳过
        if(nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 1){
            continue;
        }
        MazeTrack(nx, ny);
    }
    maze[x][y] = 0;//恢复现场,设为未走
    path_temp.pop_back();
}0
int main(){
    while(cin >> m >> n){
        maze = vector<vector<int>>(m, vector<int>(n, 0));
        path_temp.clear();
        path_best.clear();
        for(auto& i : maze){
            for(auto& j : i){
                cin >> j;
            }
        }
        MazeTrack(0, 0);//回溯寻找迷宫的最短路径
        for(auto& i : path_best){
            cout << '(' << i[0] << ',' << i[1] << ')' << endl;//输出通路
        }
    }
    return 0;
}


编辑于 2020-06-26 17:35:37 回复(0)