首页 > 试题广场 >

迷宫问题

[编程题]迷宫问题
  • 热度指数：225297 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}有一个 h 行 w 列的网格，我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格。每个方格要么是可以通过的空方格 \texttt{`0'} ，要么是不可通过的墙方格 \texttt{`1'} ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 (x,y) 向上移动一格即抵达 (x-1,y) 、向下移动一格即抵达 (x+1,y) 、向左移动一格即抵达 (x,y-1) 、向右移动一格即抵达 (x,y+1) 。
\hspace{15pt}现在，你位于迷宫的入口 (0,0) ，想要前往终点 (h-1,w-1) 。请输出一条从起点到终点的可行路径。

\hspace{15pt}保证起点和终点一定为空方格，你始终可以找到且能唯一找到一条从起点出发到达终点的可行路径。

输入描述:
\hspace{15pt}第一行输入两个整数 h,w\left(1 \leqq h, w \leqq 100\right) 代表迷宫的行数和列数。
\hspace{15pt}此后 h 行，第 i 行输入 w 个整数 a_{i,1}, a_{i,2}, \dots, a_{i,w}\left(0 \leqq a_{i,j} \leqq 1\right) 代表迷宫的布局。其中，a_{i,j}=0 表示单元格 (i,j) 是空方格，a_{i,j}=1 表示单元格 (i,j) 是墙方格。


输出描述:
\hspace{15pt}输出若干行，第 i 行输出两个整数 x_i,y_i ，表示路径的第 i 步抵达的单元格坐标为 (x_i,y_i) 。

\hspace{15pt}你需要保证输出的路径是符合题目要求的，即从起点 (0,0) 出发，到达终点 (h-1,w-1) ，且路径上每个单元格都是空方格，行走的单元格都是彼此相邻的。
示例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)
算法知识视频讲解
添加回答
Java
笔寞头像 笔寞 
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)
C/C++
AhrensK头像 AhrensK
从起点开始不断四个方向探索，直到走到出口，走的过程中我们借助栈记录走过路径的坐标，栈记录
坐标有两方面的作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯找其他的通路。 
#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)
henryboy233头像 henryboy233 
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)
Java
七·喜头像 七·喜 
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)
C/C++
୧(๑•̀ㅁ•́๑)૭✧头像 ୧(๑•̀ㅁ•́๑)૭✧
题目要求：路径唯一，则不是寻找最优路径，而是寻找唯一路径且数据规模不大，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)
SunriseKY头像 SunriseKY 
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)
Java
305602188头像 305602188 
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
牛客459537429号头像 牛客459537429号
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)
Java
牛客35031561号头像 牛客35031561号

深度优先遍历搜索。
从（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)
C/C++
WZ_Dale头像 WZ_Dale
本题可用回溯法求解 具体步骤为：
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)
Java
面向代码编程头像 面向代码编程
考虑前后左右情况的java解法 
import java.util.Scanner;
import java.util.ArrayList;

public class Main{
    public static ArrayList<String>list=new ArrayList<>();
    public static ArrayList<String>best=new ArrayList<>();

    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            list.clear();
            best.clear();
            int h=sc.nextInt();
            int l=sc.nextInt();
            int arr[][]=new int[h][l];
            for(int i=0;i<h;i++){
                for(int j=0;j<l;j++){
                    arr[i][j]=sc.nextInt();
                }
            }
            MazeTrack(arr,0,0);
           // System.out.println(best.toString());
            for(int i=0;i<best.size();i++){
                System.out.println(best.get(i));
            }

        }
    }

    public static void MazeTrack(int[][]arr, int x, int y){
        list.add("("+x+","+y+")");
        //System.out.println(list.toString());
        arr[x][y]=1;
        int h=arr.length;
        //System.out.println(h);
        int l=arr[0].length;
       // System.out.println(l);
        if(x==h-1&&y==l-1){
            if(best.size()==0||list.size()<best.size()) {
                best.clear();
                for(int i=0;i<list.size();i++)
                best.add(list.get(i));
            }
            //System.out.println(best);
        }
        if(x-1>=0&&arr[x-1][y]==0){
            MazeTrack(arr,x-1,y);
        }
        if(y-1>=0&&arr[x][y-1]==0){
            MazeTrack(arr,x,y-1);
        }
        if(x+1<h&&arr[x+1][y]==0){
            MazeTrack(arr,x+1,y);
        }
        if(y+1<l&&arr[x][y+1]==0){
            MazeTrack(arr,x,y+1);
        }
        arr[x][y]=0;
        list.remove("("+x+","+y+")");
        //System.out.println(best);

    }
}

发表于 2020-05-05 20:24:30 回复(0)
felix_duan头像 felix_duan 
#include<iostream>
#include<vector>
using namespace std;
void MiGong(vector<vector<int> > matrix, vector<int>& res, vector<int>& vec_temp,int row, int col){
    vec_temp.push_back(row);
    vec_temp.push_back(col);
    matrix[row][col]=1;
    if(row==matrix.size()-1&&col==matrix[0].size()-1){
        if(res.empty() || vec_temp.size()<res.size()){
            res.clear();
            res.insert(res.begin(),vec_temp.begin(),vec_temp.end());
        }
    }
    else {
        // 往下走
        if (row + 1 <= matrix.size() - 1 && matrix[row + 1][col] == 0) {
            MiGong(matrix, res, vec_temp, row + 1, col);
            vec_temp.pop_back();
            vec_temp.pop_back();
            matrix[row + 1][col] = 0;
        }
        // 往上走
        if (row - 1 >= 0 && matrix[row - 1][col] == 0) {
            MiGong(matrix, res, vec_temp, row - 1, col);
            vec_temp.pop_back();
            vec_temp.pop_back();
            matrix[row - 1][col] = 0;
        }
        // 往右走
        if (col + 1 <= matrix[0].size() - 1 && matrix[row][col + 1] == 0) {
            MiGong(matrix, res, vec_temp, row, col + 1);
            vec_temp.pop_back();
            vec_temp.pop_back();
            matrix[row][col + 1] = 0;
        }
        // 往左走
        if (col - 1 >= 0 && matrix[row][col - 1] == 0) {
            MiGong(matrix, res, vec_temp, row, col - 1);
            vec_temp.pop_back();
            vec_temp.pop_back();
            matrix[row][col - 1] = 0;
        }
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        int temp;
        vector<vector<int> > matrix(n,vector<int>(m,0));
        vector<int> res;
        vector<int> vec_temp;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cin>>temp;
                matrix[i][j]=temp;
            }
        }
        MiGong(matrix, res, vec_temp,0, 0);
        for(int i=0; i<res.size(); i++){
            cout<<'('<<res[i]<<','<<res[i+1]<<')'<<endl;
            i++;
        }
    }
    return 0;
}

编辑于 2020-03-22 23:11:56 回复(0)
我回去等通知了头像 我回去等通知了 
//这题使用的是bfs，这里有几个你不能错过的广搜的技巧：
//1 构造队列记录路径
//2 先将周围一圈都设置为已经访问过，这样不用判断是否会越界
//3 移动的方向不用写8个int,直接int dir[5] = {1,0,-1,0,1};
//3  这样每次是+dir[i],+dir[i+1]

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

int n,m;
const int maxn  = 15;
bool vis[maxn][maxn];
int maze[maxn][maxn];

struct pos
{
    int r,c;
    int father;
    pos(int _r = 0,int _c = 0,int _f = 0):r(_r),c(_c),father(_f){}
};

int dir[5] = {1,0,-1,0,1};
void bfs()
{
    pos q[120];

    //自己构造队列来实现广搜
    int head = 0,tail = 1;
    q[head] = pos(1,1,-1);
    vis[1][1] = true;
    int cnt = 0;
    while(head != tail)
    {
        pos f = q[head];
        if(f.r == n && f.c == m)
        {
            //找到了
            vector<pos> vt;
            while(true)
            {
                vt.push_back(f);
                if(f.father == -1)
                    break;
                f = q[f.father];
            }
            for(int i = vt.size()-1; i >= 0; --i)
            {
                cout << "(" << vt[i].r-1 << "," << vt[i].c-1 << ")"<< endl;
            }
            break;
        }
        for(int i = 0; i < 4; ++i)
        {
            int newR = dir[i] + f.r;
            int newC = dir[i+1] + f.c;

            if(!vis[newR][newC] && maze[newR][newC] == 0)
            {
                vis[newR][newC] = true;
                q[tail++] = pos(newR,newC,head);
            }
        }

        ++head;
    }

}

int main(){
#ifdef ONLINE_JUDGE
#else
	 freopen("E:/input.txt", "r", stdin);
#endif

    while(cin >> n >> m)
    {
        fill(vis[0],vis[0]+maxn*maxn,true);

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                cin >> maze[i][j];
                vis[i][j] = false;
            }
        }
        bfs();
    }
    return 0;
}


编辑于 2020-03-14 23:11:46 回复(0)
小小科研虫头像 小小科研虫 
//基于剑指offer获取思路,采用回溯法进行解答


	#include<iostream>
#include<vector>





	using namespace std;
bool HasPathCore(vector<vector<int>>& maze,int row,int col,vector<vector<bool>> &visit,vector<vector<int>>&res)
{
    bool hasPath=false;
    int rows=maze.size();
    int cols=maze[0].size();
    //递归的终止条件
    if(row==rows-1 && col==cols-1)
    {
        vector<int> cur;
        cur.push_back(row);
        cur.push_back(col);
        res.push_back(cur);
        return true;
    }
    if(row>=0 && row<rows && col>=0 && col<cols && maze[row][col]==0 && visit[row][col]==false)
    {
        visit[row][col]=true;
        
        vector<int> cur;
        cur.push_back(row);
        cur.push_back(col);
        res.push_back(cur);
        
        hasPath=HasPathCore(maze,row,col-1,visit,res)||
            HasPathCore(maze,row-1,col,visit,res)||
            HasPathCore(maze,row,col+1,visit,res)||
            HasPathCore(maze,row+1,col,visit,res);
        
        if(!hasPath)
            visit[row][col]=false;
    }
    return hasPath;
}





	int main()
{
    int N,M;
    while(cin>>N>>M)
    {
        vector<vector<int>> maze(N,vector<int>(M,0));
        vector<vector<bool>> visit(N,vector<bool>(M,false));
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                cin>>maze[i][j];
            }
        }
        
        vector<vector<int>> res;
        
        if(HasPathCore(maze,0,0,visit,res))
        {
            for(int i=0;i<res.size();i++)
            {
                cout<<"("<<res[i][0]<<','<<res[i][1]<<')'<<endl;
            }
        }
    }
    return 0;
}

发表于 2019-07-31 22:00:31 回复(0)
OrientObjectPro头像 OrientObjectPro 
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<ctype.h>

using namespace std;

void dfs(int x,int y,stack<string> s);// 深度搜索 s用来存放坐标路径
bool check_ok(int x,int y);          // 判断每个坐标是否可行（剪枝）
string to_string(int x,int y);         //把坐标转为字符串形式

vector<vector<int>> vec(11, vector<int> (11) );    //存放地图
vector<vector<int>> book(11,vector<int> (11));        //标记地图对应的点是否走过
stack<string> s;                                    //存放路径的栈，作为dfs函数的参数
stack<string> res;                                    //最终结果栈
bool flag=true;                                      //标志位

int main()
{
   while(cin>>COL>>ROW)
    {               for (int i = 0; i < 11; i++)         {             for (int j = 0; j < 11; j++)             {                 vec[i][j]=0;                 book[i][j]=0;             }         }         flag=true;         while (!s.empty())         {             s.pop();         }  
        for(int i=0;i<=COL;i++)
        {
            for(int j=0;j<=ROW;j++)
            {
                vec[i][j]=1;
            }
        }
     
        for(int i=1;i<=COL;i++)
        {
            for(int j=1;j<=ROW;j++)
            {
                cin>>vec[i][j];
            }
        }
        
//前面的操作均为初始化操作

        string st="(0,0)";
        s.push(st);
        dfs(1,1,s);
               stack<string> last;         int leng=res.size();         for (int i = 0; i < leng; i++)         {                     last.push(res.top());             res.pop();         }                        for (int i = 0; i < leng; i++)         {             cout<<last.top()<<endl;             last.pop();         }
     
    }

    return 0;
}

void dfs(int x,int y,stack<string> s)
{
    if(x==COL&&y==ROW)
    {         if (flag)         {             flag=false;             res=s;         }         else         {             if (res.size()>s.size())             {                 res=s;             }         }            
    }
  
    else
    {
        int next[2][4]=
        {
            1,-1,0,0,
            0,0,1,-1
        };
        int tx,ty;
        for(int i=0;i<4;i++)
        {
            tx=x+next[0][i];
            ty=y+next[1][i];
            if(check_ok(tx,ty))
            {
                book[tx][ty]=2;
                s.push( to_string(tx,ty));
                dfs(tx,ty,s);
                book[tx][ty]=0;
                s.pop();
            }
        }
    }
}
bool check_ok(int x,int y)
{     if (x<1||x>COL||y<1||y>ROW)     {         return false;     }
    if(book[x][y]==2)
        return false;
    if( vec[x][y]==1  )
        return false;
    return true;
}

string to_string(int x,int y)
{    --x,--y;     char temp[10]="( , )";     char a=x+'0';     char b=y+'0';     temp[1]=a;     temp[3]=b;     string st=temp;     return st;     }

发表于 2019-05-05 12:27:45 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int N,M;
vector<vector<int>> G;
vector<vector<int>> Path;
vector<vector<int>> temp;

void T(int i, int j)
{     G[i][j] = 1;     temp.push_back({i,j});          if(i==N-1 && j==M-1)         if(Path.empty() || temp.size() < Path.size())             Path = temp;          if(i>0 && G[i-1][j]==0)         T(i-1,j);     if(i<N-1 && G[i+1][j]==0)         T(i+1,j);     if(j>0 && G[i][j-1]==0)         T(i,j-1);     if(j<M-1 && G[i][j+1]==0)         T(i,j+1);              G[i][j] = 0;     temp.pop_back();
}
 
int main()
{     while(cin>>N>>M)      {         G = vector<vector<int>> (N,vector<int>(M,0));         Path.clear();         temp.clear();         for(int i=0;i<N;i++)             for(int j=0;j<M;j++)                 cin>>G[i][j];         T(0,0);         for(int i=0;i<Path.size();i++)             printf("(%d,%d)\n", Path[i][0], Path[i][1]);          }     return 0;
}

发表于 2019-01-06 00:26:29 回复(0)
无敌的白金之星头像 无敌的白金之星 
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

int map[11][11];
pair<int, int> path[11][11];
int d[4][2] = { {-1, 0}, {0,-1}, {0, 1}, {1, 0} };

void bfs(int m, int n)
{
    queue<pair<int, int>> que;
    que.push({ 0, 0 });
    while (!que.empty())
    {
        pair<int, int> p = que.front();
        que.pop();
        if (p.first == m - 1 && p.second == n - 1) break;
        for (int i = 0; i < 4; ++i)
        {
            int x = p.first + d[i][0];
            int y = p.second + d[i][1];
            if (x >= 0 && x < m && y >= 0 && y < n && map[x][y] == 0)
            {
                que.push({ x, y });
                path[x][y] = { p.first, p.second };
                map[x][y] = 1;
            }
        }
    }
}

int main()
{
    int m, n;
    while (cin >> m >> n)
    {
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                cin >> map[i][j];
        bfs(m, n);
        stack<pair<int, int>> s;
        pair<int, int> p = path[m - 1][n - 1];
        s.push({ m - 1, n - 1 });
        s.push(p);
        while (true)
        {
            p = path[p.first][p.second];
            s.push(p);
            if (p.first == 0 && p.second == 0)
                break;
        }
        while (!s.empty())
        {
            pair<int, int> p = s.top();
            s.pop();
            cout << "(" << p.first << "," << p.second << ")" << endl;
        }
    }
}

发表于 2018-11-28 12:37:43 回复(0)
萤火^虫头像 萤火^虫
步骤：（假设坐标为[i，j]）（用一个栈保存经过的路径，即保存经过的坐标）（mat表示迷宫坐标）
1、横向走，直到下一步碰到墙壁（题目中用1表示）或者要越界了
2、竖向走，直到下一步碰到墙壁或者要越界了
3、在条件1和条件2不满足情况下，即(i+1,j) 和(i, j+1)碰到墙壁或者要越界了，mat[i][j] = 1。同时出栈，并让它的坐标值赋值给当前 i 和当前的 j 。
代码如下： 
while True:
    try:
        def islegal(i, j, mat):#检测坐标是否合法
            if i < 0 or i >= len(mat):
                return 0
            if j < 0 or j >= len(mat[0]):
                return 0
            if mat[i][j] == 1:
                return 0
            return 1
        N, M = map(int, raw_input().split())
        mat = [] #迷宫矩阵
        for i in range(N):
            l = list(map(int, raw_input().split()))
            mat.append(l)
        i = 0
        j = 0
        sign = 1
        path = []
        while sign:
            if islegal(i, j, mat):
                path.append([i, j])
                if islegal(i, j + 1, mat):#横向遍历，即步骤1
                    j += 1
                elif islegal(i + 1, j, mat):#竖向遍历，即步骤2
                    i += 1
                elif islegal(i + 1, j, mat) == 0 and islegal(i, j + 1, mat) == 0:#在1和2不满足情况下，进行出栈等操作即步骤3
                    mat[i][j] = 1 #因为当前位置走不通，所以设为1。表示在以后的运行中绕开它
                    tmp = path[-2]#出栈，自所以是倒数第二个，是因为，当前位置也添加到栈中了
                    del path[-1]
                    del path[-1]
                    i = tmp[0]
                    j = tmp[1]
            if i == (len(mat) - 1) and j == (len(mat[0]) - 1):
                sign = 0
                path.append([i, j])
        for i in range(len(path)):
            print("(%d,%d)" % (path[i][0], path[i][1]))
    except:
        break

发表于 2018-09-16 22:35:58 回复(2)
QiLuYa头像 QiLuYa 
/**
 * Notes:下面算法得到的路线只是一种可行的路线。它不一定是最短路线。
 */

#include <stdio.h>


//检查某个坐标是否与栈中存储的历史坐标相重复
int CheckRepeat(int x, int y, int *s, int top) {
    int i;

    for(i=1 ; i<top ; i+=3) {
        if(s[i+1]==x && s[i]==y)
            return 1;
    }
    return 0;
}

#define MAZE_SIZE 10
#define STACK_SIZE (3*MAZE_SIZE*MAZE_SIZE+1)

void PrintWayOutOfMaze(int m[MAZE_SIZE][MAZE_SIZE], int row, int col)
{
    //回溯类问题，一般需要用栈来保存历史信息，比如二叉树的遍历
    int s[STACK_SIZE]; 
    int top;

    int x, y, d;
    int i, j;

    x = 0, y = 0, d = 0, top = 0, s[0] = 0;

    while(1) {
        //判断朝哪个方向前进一格，以向右为优先方向。判断条件有4个。CheckRepeat用来防止在迷宫的一个环路上无限循环下去。
        if(1>d && y<col-1 && m[x][y+1]==0 && !CheckRepeat(x, y+1, s, top)) {
            top += 3;
            s[top-2] = y;  //每次入栈3个元素，除了y，x，还有一个用来表示前进方向的变量d（右、下、左，上，依此编码为1,2,3,4）
            s[top-1] = x;
            s[top] = 1;
            y++;
            d = 0;
        } else if(2>d && x<row-1 && m[x+1][y]==0 && !CheckRepeat(x+1, y, s, top)) {
            top += 3;
            s[top-2] = y;
            s[top-1] = x;
            s[top] = 2;
            x++;
            d = 0;
        } else if(3>d && y>0 && m[x][y-1]==0 && !CheckRepeat(x, y-1, s, top)) {
            top += 3;
            s[top-2] = y;
            s[top-1] = x;
            s[top] = 3;
            y--;
            d = 0;
        } else if(4>d && x>0 && m[x-1][y]==0 && !CheckRepeat(x-1, y, s, top)) {
            top += 3;
            s[top-2] = y;
            s[top-1] = x;
            s[top] = 4;
            x--;
            d = 0;
        } else {  //如果不能前进，则退一步，即出栈。此处会刷新d，下一次判断前进方向时，只能选比d大的值对应的方向。
            if(top == 0) {
                printf("There is no way out of the maze.\n");
                break;
            }
            top -= 3;
            y = s[top+1];
            x = s[top+2];
            d = s[top+3];
        }

        if(x==row-1 && y==col-1) {
            for(i=1 ; i<top ; i+=3)
                printf("(%d,%d)\n", s[i+1], s[i]);
            printf("(%d,%d)\n", row-1, col-1);
            break;
        }
    }
}


int main()
{
    int row, col;
    int res;
    int i, j;
    int m[MAZE_SIZE][MAZE_SIZE];

    while(1) {
        res = scanf("%d", &row);
        if(res == EOF) break;

        scanf("%d", &col);
        for(i=0 ; i<row ; i++)
            for(j=0 ; j<col ; j++)
                scanf("%d", &m[i][j]);

        PrintWayOutOfMaze(m, row, col);
    }
}

发表于 2018-05-31 19:19:37 回复(0)
提交观点

问题信息

dfs 查找 广度优先搜索(BFS)
难度：
630条回答 108989浏览

热门推荐

通过挑战的用户

查看代码

相关试题

迷宫问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号