首页 > 试题广场 >

游戏地图路径

[编程题]游戏地图路径

热度指数：2958 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为 n*n 的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的(比如建筑、高山、河流或者其它障碍物等)，现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，以协助运营小伙伴评估该游戏的可玩性和上手难度。

数据范围： $5\le n \le 1000\$

进阶：时间复杂度 $O(n^2)\$ ，空间复杂度 $O(n^2)\$

输入描述:

第一行表示矩阵大小 n，5 第二行表示起点和终点的坐标
第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，其他字母、非0数字、以及符号+、-、* 等等均表示普通可达格子，共有 n 行  n 列

输出描述:

输出最优路径的长度；若无法到达，则输出-1

示例1

输入

15
0 7 7 7
*5#++B+B+++++$3
55#+++++++###$$
###$++++++#+*#+
++$@$+++$$$3+#+
+++$$+++$+4###+
A++++###$@+$++A
+++++#++$#$$+++
A++++#+5+#+++++
+++$$#$++#++++A
+++$+@$###+++++
+###4+$+++$$+++
+#+3$$$+++$##++
+#*+#++++++#$$+
$####+++++++$##
3$+++B++B++++#5

输出

备注:

最优即最短，寻找最优路径时只能按上下左右四个方向前进。

算法知识视频讲解

白桃呜龙呀

深度优先搜索DFS（与剑指offer机器人思想类似）但这题需要考虑上下左右

def dfs(x, y, grid, endx, endy, visited, count):
    if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] in "#@" \
            or (visited[x][y] != 0 and visited[x][y] <= count):
        return
    visited[x][y] = count
    if x == endx and y == endy:
        return
    dfs(x, y + 1, grid, endx, endy, visited, count + 1)
    dfs(x, y - 1, grid, endx, endy, visited, count + 1)
    dfs(x - 1, y, grid, endx, endy, visited, count + 1)
    dfs(x + 1, y, grid, endx, endy, visited, count + 1)


if __name__ == "__main__":
    n = int(input())
    [starty,startx,endy,endx] = list(map(int,input().split()))
    road = []
    for i in range(n):
        road.append(list(input()))
    visited = [[0]*n for _ in range(n)]
    dfs(startx,starty,road,endx,endy,visited,1)
    print(visited[endx][endy]-1)

发表于 2021-04-11 15:00:39 回复(1)

山水相逢处

package com.cnblogs;


import java.util.*;


public class Main{

    private static Queue<Posi> q = new LinkedList<Posi>();
    private static int[][] dir = {{0,1},{0,-1},{-1,0},{1,0}};//方向
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        String[] map = new String[N];
        int [][] vis = new int[N][N];//访问位...
//        for(int i = 0;i<vis.length;i++){
//            System.out.println(Arrays.toString(vis[i]));
//        }
//        System.out.println("--------------------");
        int y1 = in.nextInt(),x1 = in.nextInt(),y2 = in.nextInt(),x2 = in.nextInt();
//        System.out.println(x1 + "," + y1 + "," + x2 + "," + y2);
//        System.out.println("--------------------");
        in.nextLine();
        for(int i = 0;i<N;i++){
            map[i] = in.nextLine();
        }

        System.out.println(bfs(map,vis,x1,y1,x2,y2));
//        for(int i = 0;i<vis.length;i++){
//            System.out.println(Arrays.toString(vis[i]));
//        }
//        for(int i = 0;i<dir.length;i++){
//            System.out.println(Arrays.toString(dir[i]));
//        }
    }

    private static int bfs(String[] map,int[][] vis,int x1,int y1,int x2,int y2){
        q.add(new Posi(x1,y1,0));
        vis[x1][y1] = 1;
        Posi local = null;
        int x,y;
        while(!q.isEmpty()){
            local = q.poll();
            for(int i = 0;i<4;i++){
                x = local.x + dir[i][0];//下一个要迭代的位置
                y = local.y + dir[i][1];
//                System.out.println(x + "," + y);
                if(inBoundary(x,y,map.length) && vis[x][y] == 0 && canThrough(map,x,y)){//can访问
                    vis[x][y] = 1;
                    if(x == x2 && y == y2){
                        return local.z + 1;
                    }
                    q.offer(new Posi(x,y,local.z + 1));
//                    System.out.println(x + "," + y + "," + (local.z + 1));
                }
            }
        }
        return -1;
    }
    private static boolean canThrough(String[] map,int x,int y){
        if(map[x].charAt(y) !='#' && map[x].charAt(y) != '@'){
            return true;
        }
        return false;
    }
    private static boolean inBoundary(int x,int y,int N){
        if(x >=0 && x<N && y >=0 && y<N){
            return true;
        }else{
            return false;
        }
    }

    private static class Posi{
        public int x;
        public int y;
        public int z;
        public Posi(){}
        public Posi(int x, int y,int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
}

发表于 2021-04-24 11:33:15 回复(0)

pein531

首先感谢一楼同学的提醒，不然我要debug到天荒地老。这种走迷宫的题一般用宽搜来求解比较好理解，在BFS的过程中，每一步都要尝试上下左右4个方向，并将可行的方向加入到队列中进行下一轮搜索，为了记忆每一步的累积步数（便于到达终点时输出步数），构建一个节点对象来记录。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

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

public class Main {
    private static int path = Integer.MAX_VALUE;
    private static int[] dx = new int[]{0, 0, 1, -1};
    private static int[] dy = new int[]{1, -1, 0, 0};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] params = br.readLine().split(" ");
        int startCol = Integer.parseInt(params[0]);
        int startRow = Integer.parseInt(params[1]);
        int endCol = Integer.parseInt(params[2]);
        int endRow = Integer.parseInt(params[3]);
        char[][] graph = new char[n][n];
        for(int i = 0; i < n; i++)
            graph[i] = br.readLine().toCharArray();
        int m = graph[0].length;
        boolean[][] visited = new boolean[n][m];
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(startRow, startCol));    // 队列用于存储下一步所有可能的位置
        visited[startRow][startCol] = true;
        int steps = 0;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(cur.x == endRow && cur.y == endCol){
                System.out.println(cur.steps);
                return;
            }
            // 走一步(尝试4个方向)
            for(int i = 0; i < 4; i++){
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];
                if(x < 0 || x >= n ||
                  y < 0 || y >= m ||
                  visited[x][y] || 
                  graph[x][y] == '@' || graph[x][y] == '#'){
                    // 越界，走过或格子不可达就跳过
                    continue;
                }else{
                    // 否则当前的格子就是下一步的候选
                    Node next = new Node(x, y);
                    next.steps = cur.steps + 1;
                    queue.offer(next);
                    visited[x][y] = true;
                }
            }
        }
        System.out.println(-1);
    }
}

发表于 2021-08-21 13:10:03 回复(0)

love_Haiyan

DFS+记忆化搜索（不加记忆化超时）

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void dfs(vector<vector<char>>& in,int i,int j,int endx,int endy,int count,vector<vector<int>>& visited){
    if(i>=in.size()||i<0||j>=in[0].size()||j<0) return ;
    if(in[i][j]=='#'||in[i][j]=='@'||(visited[i][j]!=0&&count>=visited[i][j])) return;

    visited[i][j]=count;
    if(i==endx&&j==endy){
        return;
    }
    
    char c=in[i][j];
    in[i][j]='#';
    dfs(in,i+1,j,endx,endy,count+1,visited);
    dfs(in,i-1,j,endx,endy,count+1,visited);
    dfs(in,i,j+1,endx,endy,count+1,visited);
    dfs(in,i,j-1,endx,endy,count+1,visited);
    in[i][j]=c;
}


int main(){
    int n;
    cin>>n;
    //输入输出
    int startx=0,starty=0,endx=0,endy=0;
    cin>>starty>>startx>>endy>>endx;
    vector<vector<char>> in(n,vector<char>(n));
    vector<vector<int>> visited(n,vector<int>(n));
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin>>in[i][j];
        }
    }
    int res=INT_MAX;
    dfs(in,startx,starty,endx,endy,1,visited);
    if(visited[endx][endy]==0) cout<<-1<<endl;
    else cout<<visited[endx][endy]-1<<endl;
    return 0;
}

发表于 2021-06-16 21:52:33 回复(0)

黑衣骑士naruto

#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
struct Step {
    int x, y;   //位置
    int steps;   //从起点开始走到x,y处需要的步数
    Step(int xx, int yy, int st) :x(xx), y(yy), steps(st) {}
};
queue<Step> q;
int main()
{
    int n;
    cin >> n;
    int a, b, c, d;
    cin >> b >> a >> d >> c;  //输入的数据是先列后行。。。
    vector<vector<char> > v;
    for (int i = 0; i < n; ++i)
    {
        vector<char> vv;
        for (int j = 0; j < n; ++j)
        {
            char tmp;
            cin >> tmp;
            vv.push_back(tmp);
        }
        v.push_back(vv);
    }
    //判重标记
    int visited[1000][1000];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            visited[i][j] = 0;
    
    int minlen = (1 << 30);
    q.push(Step(a, b, 0));   //起点入队列
    visited[a][b] = 1;
    while (!q.empty())
    {
        Step s = q.front();
        if (s.x == c && s.y == d)   //到出口了
        {
            minlen = s.steps;
            break;
        }        
        else
        {
            if (s.y - 1>=0 && v[s.x][s.y - 1] != '#' && v[s.x][s.y - 1] != '@' && !visited[s.x][s.y - 1])  //如果可以往左走
            {
                q.push(Step(s.x, s.y - 1, s.steps + 1));
                visited[s.x][s.y - 1] = 1;
            }
            if (s.y + 1 <= n - 1 && v[s.x][s.y + 1] != '#' && v[s.x][s.y + 1] != '@' && !visited[s.x][s.y + 1])  //如果可以往右走
            {
                q.push(Step(s.x, s.y + 1, s.steps + 1));
                visited[s.x][s.y + 1] = 1;
            }
            if (s.x - 1>=0 && v[s.x-1][s.y] != '#' && v[s.x-1][s.y] != '@' && !visited[s.x-1][s.y])  //如果可以往上走
            {
                q.push(Step(s.x-1, s.y, s.steps + 1));
                visited[s.x - 1][s.y] = 1;
            }
            if (s.x + 1 <=n-1 && v[s.x + 1][s.y] != '#' && v[s.x + 1][s.y] != '@' && !visited[s.x + 1][s.y])  //如果可以往下走
            {
                q.push(Step(s.x + 1, s.y, s.steps + 1));
                visited[s.x + 1][s.y] = 1;
            }
            q.pop();
        }
    }
    if (minlen == (1 << 30))
        minlen = -1;
    cout << minlen << endl;
    return 0;
}

发表于 2021-04-17 17:29:11 回复(1)

Python

牛客589187471号

迷宫问题寻找最短路径，用广度优先搜索

from collections import deque
def solution():
    n = int(input().strip())
    y0, x0, y1, x1 = [int(x) for x in input().split(" ")]
    M = []
    step = 0
    flag = 0
    for _ in range(n):
        M.append([x for x in input().strip()])

    que = deque([[x0, y0]])
    M[x0][y0] = "0"
    while que:
        c = len(que)
        step += 1
        for _ in range(c):
            cur_x, cur_y = que.popleft()
            for a, b in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                next_x, next_y = cur_x + a, cur_y + b
                if next_x == x1 and next_y == y1:
                    if M[next_x][next_y] not in "0#@":
                        print(step)
                        flag = 1
                        return
                    else:
                        print(-1)
                        return
                if 0 <= next_x < n and 0 <= next_y < n and M[next_x][next_y] not in "0#@":
                    que.append([next_x, next_y])
                    M[next_x][next_y] = "0"
    if flag == 0:
        print(-1)
solution()

发表于 2021-04-09 23:20:18 回复(0)

牛客271461776号

public class Main {

  private static int[][] posi = new int[][] { { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
  static int len;
  static int start_y;
  static int start_x;
  static int end_y;
  static int end_x;
  static int[][] map;
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    len = in.nextInt();
    start_y = in.nextInt();
    start_x = in.nextInt();
    end_y = in.nextInt();
    end_x = in.nextInt();
    int[][] grid = new int[len][len];
    for (int i = 0; i < len; i++) {
      String row = in.next();
      for (int j = 0; j < len; j++) {
        if (row.charAt(j) == '#' || row.charAt(j) == '@')
          grid[i][j] = -1;
      }
    }

    map = new int[len][len];
    for (int i = 0; i < map.length; i++)
      Arrays.fill(map[i], Integer.MAX_VALUE);
    calcWayDistance(grid, start_x, start_y, 0);
    if(map[end_x][end_y] == Integer.MAX_VALUE){
      System.out.println(-1);
    }else{
      System.out.println(map[end_x][end_y]);
    }

  }

  private static void calcWayDistance(int[][] grid, int x, int y, int dis) {
    if(x<0||x>=len||y<0||y>=len||grid[x][y] == -1||dis>=map[x][y])
      return;
    map[x][y] = dis;
    for(int[] dir:posi){
      int xx = x+dir[0];
      int yy = y+dir[1];
      calcWayDistance(grid, xx, yy, dis+1);
    }
  }

}

发表于 2021-04-08 13:55:26 回复(0)

call_me_Siven

题目的始末点坐标的行和列是反过来的

import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] map = new int[n][n];
        int start_y = sc.nextInt();
        int start_x = sc.nextInt();
        int end_y = sc.nextInt();
        int end_x = sc.nextInt();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < n; j++) {
                char c = s.charAt(j);
                if (c == '#' || c == '@') {
                    map[i][j] = 1;
                }
            }
        }
        Solution sol = new Solution(map, n, end_x, end_y);
        sol.dfs(start_x, start_y, 0);
        System.out.println(sol.getAns());
    }
}

class Solution {
    private int[][] record;
    private int[][] map;
    private int end_x;
    private int end_y;
    private int n;
    private int[][] direction = {{1,0},{0,1},{-1,0},{0,-1}};
    public Solution(int[][] map, int n, int x, int y) {
        this.map = map;
        this.n = n;
        record = new int[n][n];
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++)
                record[i][j] = Integer.MAX_VALUE;
        end_x = x;
        end_y = y;
    }
    public void dfs(int x, int y, int d) {
        record[x][y] = d;
        for (int[] dir : direction) {
            int xx = dir[0] + x;
            int yy = dir[1] + y;
            if (!isValid(xx, yy, d+1)) continue;
            dfs(xx, yy, d+1);            
        }
    }
    public boolean isValid(int x, int y, int d) {
        return x >= 0 && x < n && y >= 0 && y < n && record[x][y] > d && map[x][y] == 0;
    }
    public int getAns() {
        return record[end_x][end_y] == Integer.MAX_VALUE? -1 : record[end_x][end_y];
    }
}

发表于 2021-03-29 16:59:58 回复(0)

励志要变胖的人

注意起点和终点坐标的行和列是反的

编辑于 2021-03-31 13:29:11 回复(9)

6cdh

BFS

#include <bits/stdc++.h>
 
using namespace std;
 
using pii = pair<int, int>;
 
int main() {
    int n;
    cin >> n;
 
    pii s;
    pii e;
 
    cin >> s.second >> s.first >> e.second >> e.first;
    string tmp;
    getline(cin, tmp);
 
    vector<string> m;
    for (int i = 0; i != n; ++i) {
        getline(cin, tmp);
        m.emplace_back(move(tmp));
    }
 
    int step = 0;
    deque<deque<bool>> visited(n, deque<bool>(n, false));
    pii direct[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
    queue<pii> q({s});
    visited[s.first][s.second] = true;
    while (!q.empty()) {
        const int sz = q.size();
        for (int i = 0; i != sz; ++i) {
            const auto node = q.front();
            q.pop();
            if (node.first == e.first && node.second == e.second) {
                cout << step;
                return 0;
            }
            for (int j = 0; j != 4; ++j) {
                auto nn = node;
                nn.first += direct[j].first;
                nn.second += direct[j].second;
                if (0 <= nn.first && nn.first < n && 0 <= nn.second &&
                    nn.second < n && m[nn.first][nn.second] != '#' &&
                    m[nn.first][nn.second] != '@' &&
                    !visited[nn.first][nn.second]) {
                    q.push(nn);
                    visited[nn.first][nn.second] = true;
                }
            }
        }
        ++step;
    }
    cout << -1;
}

发表于 2021-03-26 11:06:48 回复(0)

openallzzz

输入给出的起点与终点坐标反了

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, INF = 0x3f3f3f3f;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, sx, sy, tx, ty;
char g[N][N];
int dist[N][N];

int main() {
    cin >> n >> sy >> sx >> ty >> tx;
    for(int i = 0; i < n; i ++) cin >> g[i];

    queue<PII> que;
    que.push({sx, sy});

    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;

    while(que.size()) {
        auto tt = que.front(); que.pop();
        for(int i = 0; i < 4; i ++) {
            int a = tt.x + dx[i], b = tt.y + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < n && g[a][b] != '#' && g[a][b] != '@') {
                if(dist[a][b] > dist[tt.x][tt.y] + 1) {
                    que.push({a, b});
                    dist[a][b] = dist[tt.x][tt.y] + 1;
                }
            }
        }
    }

    if(dist[tx][ty] == INF) puts("-1");
    else cout << dist[tx][ty] << "\n";

    return 0;
}

发表于 2023-02-07 23:06:00 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int y1 = in.nextInt(), x1 = in.nextInt(), y2 = in.nextInt(), x2 = in.nextInt();
        String[] board = new String[n];
        in.nextLine();
        for (int i = 0; i < n; i++) {
            board[i] = in.nextLine();
        }
        int res = fun(x1, y1, x2, y2, board);
        System.out.println(res);
    }
    // bfs处理
    static int[][] d = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
    public static int fun(int x1, int y1, int x2, int y2, String[] board) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        boolean[][] v = new boolean[board.length][board.length];
        v[x1][y1] = true;
        q.offer(new int[]{x1, y1});
        int dis = 0;
        while (!q.isEmpty()) {
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int[] node = q.poll();
                int x = node[0], y = node[1];
                for (int j = 0; j < 4; j++) {
                    int nx = x + d[j][0], ny = y + d[j][1];
                    if (nx == x2 && ny == y2) { // 到达终点
                        return dis+1;
                    } else if (nx >= 0 && nx < board.length && ny >= 0 && ny < board.length
              && board[nx].charAt(ny) != '#' && board[nx].charAt(ny) != '@' && !v[nx][ny]) {
                        v[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
            dis++;
        }
        return -1;
    }
}

就是这个输入坐标是反的很气人！！！

发表于 2022-06-21 23:05:18 回复(0)

C++

offer来喽！

DFS  记忆化memory

#include<iostream>
using namespace std;
#include<vector>
void dfs(const vector<vector<char>>& vec,int beginX,int beginY,int endX,int endY,const int n,vector<vector<int>>& memory,int count){
    if(beginX<0||beginX>=n||beginY<0||beginY>=n) return; // 越界
    if(vec[beginX][beginY]=='#'||vec[beginX][beginY]=='@') return;  // 障碍
    if(memory[beginX][beginY]!=0 && memory[beginX][beginY]<=count) return ; // 已经访问过或者记忆数组记录的距离更小
    memory[beginX][beginY]=count; // 记录当前距离
    if(beginX==endX && beginY==endY) return; // 到达终点
    dfs(vec, beginX-1, beginY, endX, endY,  n, memory,count+1);
    dfs(vec, beginX+1, beginY, endX, endY,  n, memory,count+1);
    dfs(vec, beginX, beginY+1, endX, endY,  n, memory,count+1);
    dfs(vec, beginX, beginY-1, endX, endY,  n, memory,count+1);  
}
int main(){
    int n=0;cin>>n;
    vector<vector<char>>vec(n,vector<char>());
    int beginX=0;int beginY=0;int endX=0;int endY=0;
    cin>>beginY>>beginX>>endY>>endX;
    for(int i=0;i<n;i++){
        string a;cin>>a;
        for(auto it:a){
            vec[i].push_back(it);
        }
    }
    vector<vector<int>> memory(n,vector<int>(n,0));
    dfs(vec,beginX,beginY,endX,endY,n,memory,1);
    if(memory[endX][endY]==0) cout<<-1<<endl;
    else cout<<memory[endX][endY]-1<<endl;
    return 0;
}

发表于 2022-04-06 13:01:51 回复(0)

牛客118490042号

在处理输入的矩阵时候我使用的是int结果半天都只通过5个用例。。。

终于调通了

算法本身还是很简单的BFS，边权为1，如果边权不为1，就只能用dijkstra+堆优化/spfa计算

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int main()
{
    int n; cin>>n;
     
    vector<string>g(n);
    //记录任一点到起点的距离，初始化为-1可以代替visited数组，表示未访问
    vector<vector<int>>dist(n,vector<int>(n,-1));
    
    int x1,y1,x2,y2;
    cin>>y1>>x1>>y2>>x2;
     
    dist[x1][y1] = 0;
     
    for(int i =0;i<n;i++)
        cin>>g[i];
    queue<PII> q;
    q.push({x1,y1});
    bool flag =false;
    while(q.size())
    {
        auto t = q.front();q.pop();
        int x = t.first, y = t.second;
            
        if(x == x2 && y == y2){
            cout<< dist[x][y];
            flag =true;
            break;
        }
        for(int i =0; i<4;i++)
        {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<n&& g[nx][ny]!='#'&&g[nx][ny]!='@' &&dist[nx][ny]==-1)
            {
                //st[nx][ny] = true;
                dist[nx][ny] =dist[x][y]+1;   
                q.push({nx,ny});
            }
        }
        
    }
    if(!flag)
        cout<< -1 <<endl;
    return 0;
}

发表于 2021-07-23 12:09:58 回复(0)

imcl

bfs：层序遍历

n = input() 
sc, sr, ec, er = map(int, raw_input().strip().split(' '))
N = n
arr = []
while N > 0:
    arr.append(raw_input().strip())
    N -= 1 
mask = [[0]*len(arr[0]) for _ in range(len(arr))]
if arr[er][ec] == '#'&nbs***bsp;arr[er][ec] == '@':
    print(-1)
else:
    dirs = [[-1,0],[1,0],[0, -1], [0, 1]]
    step = 0 
    queue = [(er, ec)]
    flag = 0 
    mask[er][ec] = 1 
    while queue:
        try:
            l = len(queue)
            for i in range(l):
                node = queue.pop(0)
                for d in dirs:
                    nr, nc = node[0] + d[0], node[1] + d[1] 
                    if nr <n and nr > -1 and nc < n and nc > -1 and mask[nr][nc] == 0:
                        mask[nr][nc] = 1 
                        if arr[nr][nc] not in ['#', '@']:
                            if nr == sr and nc == sc:
                                print(step + 1)
                                flag = 1 
                                raise 
                            else:
                                queue.append((nr, nc))
            step += 1 
        except:
            break 
    if flag == 0:
        print(-1)

编辑于 2021-07-13 09:49:21 回复(0)

牛客898857677号

参考leetcode转盘锁问题，使用广度优先搜索

发表于 2021-06-17 15:11:50 回复(0)

Mangtu

import java.util.Scanner;

public class Main {
    private static int[][] map;
    private static char[][] chars;
    private static int n;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int startY = in.nextInt(),startX = in.nextInt(),endY = in.nextInt(),endX = in.nextInt();
        chars = new char[n][n];
        map = new int[n][n];
        for (int i = 0; i < n; i++) chars[i] = in.next().toCharArray();
        dfs(startX,startY,1,endX,endY);
        System.out.println(map[endX][endY] - 1);
    }
    public static void dfs(int x,int y,int count,int endX,int endY){
        if ((x < 0 || x >= n || y < 0 || y >= n)||(chars[x][y]=='#'||chars[x][y]=='@')||(map[x][y] != 0 && map[x][y] <= count))
            return;
        map[x][y] = count;
        if (x == endX && y == endY) return;
        count ++;
        dfs(x - 1,y,count,endX,endY);
        dfs(x + 1,y,count,endX,endY);
        dfs(x,y - 1,count,endX,endY);
        dfs(x,y + 1,count,endX,endY);
    }
}
//暴力递归加一个动态规划数组

编辑于 2021-04-09 21:04:30 回复(0)

这个名字不好起

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int ans;
struct direction{//也代表点
    int row, col;
    direction(){
        ;
    }
    direction(int row, int col):row(row), col(col){
        ;
    }
    struct direction operator +(const struct direction &s){
        direction ans;
        ans.row=s.row+row;
        ans.col=col+s.col;
        return ans;
    }
};

vector<direction> direct;
vector<vector<bool> > isvisit;
int n;
bool judge(const pair<direction ,int> a,const pair<direction ,int> b){
    return a.second<b.second;
   
}
bool isvalid(direction &d){
    if(d.col<0 || d.row<0 || d.col>=n || d.row>=n) return false;
    return true;
}
void BFS(direction start, direction end, int step, vector<vector<char>> &bitmap)
{
    if(start.row==end.row && start.col == end.col){
        if(step<ans){
            ans=step;
        }
        return ;
    }
    if(ans!=(1<<30) && (abs(end.row-start.row)+abs(end.col-start.col)+step)>=ans)
        return;
    vector<pair<direction ,int>> tmp;
    for(int i=0; i<direct.size(); i++){
        direction dest=direct[i]+start;
        if(isvalid(dest) && isvisit[dest.row][dest.col]==false && bitmap[dest.row][dest.col]!='#' && bitmap[dest.row][dest.col]!='@'){
            tmp.push_back(make_pair(dest, abs(dest.row-end.row)+abs(dest.col-end.col)));
        }
    }
    sort(tmp.begin(), tmp.end(), judge);
    for(int i=0; i<tmp.size(); ++i){
        isvisit[tmp[i].first.row][tmp[i].first.col]=true;
        if(isdigit(bitmap[tmp[i].first.row][tmp[i].first.col]))
            BFS(tmp[i].first, end, step+1, bitmap);
        else
            BFS(tmp[i].first, end, step+1, bitmap);
        isvisit[tmp[i].first.row][tmp[i].first.col]=false;
    }
    

}
int main(){
  
    direction start,end;
    cin>>n;
    //cin>>start.row>>start.col>>end.row>>end.col;
    
    cin>>start.col>>start.row>>end.col>>end.row;//我真的无语了。。。
    
    vector<vector<char>> bitmap(n, vector<char>(n, '\0'));
    //isvisit=vector<vector<bool>>(n, vector<bool>(n, false));
    vector<bool> ttt(n, false);
    for(int i=0; i<n; i++){
        string str;
        cin>>str;
        isvisit.push_back(ttt);
        //cout<<str<<endl<<endl;
        for(int j=0; j<n; j++){
            //cin>>bitmap[i][j];
            bitmap[i][j]=str[j];
        }
    }
    direct.push_back(direction(1,0));
    direct.push_back(direction(-1,0));
    direct.push_back(direction(0,-1));
    direct.push_back(direction(0,1));
   
    ans=1<<30;
    isvisit[start.row][start.col]=true;
    BFS(start, end, 0, bitmap);
    
    if(ans==(1<<30)) cout<<-1;
    else cout<<ans<<endl;
    
}
这输入，我人傻了。行列反过来的

发表于 2021-04-04 17:59:04 回复(0)