vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为 n*n 的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的(比如建筑、高山、河流或者其它障碍物等)，现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，以协助运营小伙伴评估该游戏的可玩性和上手难度。
数据范围：
进阶：时间复杂度%5C)
，空间复杂度
[编程题]游戏地图路径
- 热度指数：2988 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行表示矩阵大小 n，5
输出描述:
输出最优路径的长度；若无法到达，则输出-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输出
13
备注:
最优即最短，寻找最优路径时只能按上下左右四个方向前进。
深度优先搜索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)
首先感谢一楼同学的提醒，不然我要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)
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)
#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)
迷宫问题寻找最短路径，用广度优先搜索
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)
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)
题目的始末点坐标的行和列是反过来的
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)
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)
输入给出的起点与终点坐标反了
#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)
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)
在处理输入的矩阵时候我使用的是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)
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)
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)
问题信息
通过挑战的用户
-
2023-03-05 16:12:14
-
2023-02-07 23:04:57
-
2022-10-28 02:54:09 -
2022-10-14 05:50:12
-
2022-09-16 16:06:17
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
