小强在玩一个走迷宫的游戏,他操控的人物现在位于迷宫的起点,他的目标是尽快的到达终点。
每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格,或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子,且每一次移动的目的地不能存在障碍物。
具体来说,设当前迷宫有 行 列,如果当前小强操控的人物位于点 ,那么关于点 中心对称的格子 满足 且 。
需要注意的是,对称飞行器最多使用次。
第一行两个空格分隔的正整数 ,分别代表迷宫的行数和列数。
接下来 行 每行一个长度为 的字符串来描述这个迷宫。
其中
代表通路。
代表障碍。
代表起点。
代表终点。
保证只有一个 和 一个 。
仅一行一个整数表示从起点最小花费多少时间单位到达终点。
如果无法到达终点,输出 。
4 4 #S.. E#.. #... ....
4
一种可行的路径是用对称飞行器到达 再向上走一步,再向右走一步,然后使用一次对称飞行器到达终点。
#include <bits/stdc++.h> typedef long long ll; using namespace std; struct node { int x,y,t; }; int n,m,sx,sy,ex,ey,v[505][505][6]; int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0}; char a[505][505]; queue<node>q; void bfs(int x,int y) { v[x][y][0]=1; int i,j,t,nx,ny; q.push({x,y,0}); while(q.size()) { x=q.front().x,y=q.front().y,t=q.front().t; q.pop(); for(i=0; i<5; i++) { if(i==4) { if(t<5) nx=n+1-x,ny=m+1-y,t++; else continue; } else nx=x+dx[i],ny=y+dy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&v[nx][ny][t]==0) { if(i==4) v[nx][ny][t]=v[x][y][t-1]+1; else v[nx][ny][t]=v[x][y][t]+1; if(nx==ex&&ny==ey) return; q.push({nx,ny,t}); } } } } int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j,ans=-1; cin>>n>>m; for(i=1; i<=n; i++) for(j=1; j<=m; j++) { cin>>a[i][j]; if(a[i][j]=='S') sx=i,sy=j; if(a[i][j]=='E') ex=i,ey=j; } bfs(sx,sy); for(i=0; i<6; i++) if(v[ex][ey][i]) ans=v[ex][ey][i]-1; cout<<ans; return 0; }
import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] s = scanner.nextLine().split(" "); int n = Integer.valueOf(s[0]); int m = Integer.valueOf(s[1]); int[][] map = new int[n][m]; int[][] res = new int[n][m]; int[][] fly = new int[n][m]; int aimr = 0; int aimc = 0; int startr = 0; int startc = 0; for (int i = 0; i < n; i++) { String s1 = scanner.nextLine(); for (int j = 0; j < m; j++) { char temp = s1.charAt(j); if (temp == 'S') { startr = i; startc = j; } else if (temp == 'E') { aimr = i; aimc = j; } else if (temp == '#') { map[i][j] = -1; } } } List<Integer> startList = Arrays.asList(startr, startc, 0); //bfs LinkedList<List<Integer>> lists = new LinkedList<>(); lists.add(startList); int step = 0; int[] dis = {1, 0, -1, 0, 0, 1, 0, -1}; while (lists.size() != 0) { LinkedList<List<Integer>> tempLists = new LinkedList<>(); for (List<Integer> list : lists) { int tempr = list.get(0); int tempc = list.get(1); int flyTime = list.get(2); //判断是否有效 if (tempr < 0 || tempr >= n || tempc < 0 || tempc >= m || map[tempr][tempc] != 0||flyTime>5) { continue; } //判断飞行器使用次数 if(res[tempr][tempc] ==0){ fly[tempr][tempc] =flyTime; }else { if(fly[tempr][tempc]>flyTime){ fly[tempr][tempc] =flyTime; }else { continue; } } res[tempr][tempc] = 1; //判断是否到达 if (tempr == aimr && tempc == aimc) { System.out.println(step); return; } //加入队列 tempLists.add(Arrays.asList(n - tempr - 1, m - tempc - 1, flyTime + 1)); for (int i = 0; i < 4; i++) { tempLists.add(Arrays.asList(tempr + dis[2 * i], tempc + dis[2 * i + 1], flyTime)); } } lists = tempLists; step++; } System.out.println("-1"); } }
[x, y, k]
表示从源点出发走到[x, y]
点且使用了k
次飞行器的最小步数(0 <= k <= 5)。 1
, 因此采用BFS
算法实现该分层图最短路 #include <bits/stdc++.h> #define x first #define y second using namespace std; using PII = pair<int, int>; using PPI = pair<PII, int>; const int N = 510, K = 6, INF = 0x3f3f3f3f; const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; int dist[N][N][K]; char g[N][N]; void solve(){ memset(dist, 0x3f, sizeof dist); int n, m; cin >> n >> m; PII st, ed; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) { cin >> g[i][j]; if (g[i][j] == 'S') st = {i, j}; if (g[i][j] == 'E') ed = {i, j}; } // cout << st.x << ' ' << st.y << ' ' << ed.x << ' ' << ed.y << endl; queue<PPI> qu; dist[st.x][st.y][0] = 0; qu.push({{st.x, st.y}, 0}); auto check = [&] (int nx, int ny) -> bool { return nx >= 1 and nx <= n and ny >= 1 and ny <= m; }; while (qu.size()) { auto t = qu.front(); qu.pop(); int x = t.x.x, y = t.x.y, k = t.y; for (int i = 0; i < 4; i ++ ) { int nx = x + dx[i], ny = y + dy[i]; if (check(nx, ny) and g[nx][ny] != '#' and dist[nx][ny][k] == INF) { dist[nx][ny][k] = dist[x][y][k] + 1; qu.push({{nx, ny}, k}); } } int tx = n + 1 - x, ty = m + 1 - y; if (check(tx, ty) and g[tx][ty] != '#' and k + 1 <= 5 and dist[tx][ty][k + 1] == INF) { dist[tx][ty][k + 1] = dist[x][y][k] + 1; qu.push({{tx, ty}, k + 1}); } } int ans = INF; for (int i = 0; i <= 5; i ++ ) ans = min(ans, dist[ed.x][ed.y][i]); if (ans == INF) ans = -1; cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t; // cin >> t; t = 1; while (t -- ) solve(); return 0; }
#include <bits/stdc++.h> using namespace std; struct Node{ int x; // 坐标 x int y; // 坐标 y int t; // 对称飞行器剩余次数 int s; // 步数 }; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; vector<string> board; vector<vector<int>> vis; int M, N; bool check(Node node) { return node.x >= 0 && node.x < N && node.y >= 0 && node.y < M && board[node.x][node.y] != '#' && vis[node.x][node.y] == 0; } int bfs(Node node) { queue<Node> q; q.push(node); while(!q.empty()) { Node n = q.front(); q.pop(); int x = n.x, y = n.y; if(board[x][y] == 'E') { return n.s; } for(int i = 0; i < 5; ++i) { Node temp; if(i == 4) { if(n.t > 0) { // 这里下标从 0 开始,题目中下标从 1 开始 temp.x = N - 1 - x; temp.y = M - 1 - y; temp.s = n.s + 1; temp.t = n.t - 1; } } else { temp.x = x + dx[i]; temp.y = y + dy[i]; temp.s = n.s + 1; temp.t = n.t; } if(check(temp)) { vis[temp.x][temp.y] = 1; q.push(temp); } } } return -1; } int main() { cin >> N >> M; board = vector<string>(N); vis = vector<vector<int>>(N, vector<int>(M)); for(int i = 0; i < N; ++i) { cin >> board[i]; } for(int i = 0; i < N; ++i) { for(int j = 0; j < M; ++j) { if(board[i][j] == 'S') { vis[i][j] = 1; Node node = {i, j, 5, 0}; cout << bfs(node) << endl; return 0; } } } }
这道题我们先分析一下,如果没有对称飞行器,就是一道普通广搜题。但是加了飞行器,如果飞行次数没有限制,也是一道普通广搜题只是除了四个direction多了一个分支。可是飞行器有次数限制。那么如果用(x,y)点的状态应该再加一个维度:飞行次数z。因为当z1不等于z2时,P(x,y,z1)和Q(x,y,z2)是两种不同的状态。
假设z1<z2,即P和Q在相同的横纵坐标,但是P剩余的飞行次数更多。level1是P已经走的步数, level2是Q走的步数。如果level1<level2。假设从(x,y,z2)走到终点的最优解是n步,容易想到,从(x,y,z1)一定可以走n步到达终点。此时P状态走到最优点的步数更少。所以在层次遍历的最优解中不该包含z2.
也就是说在向z增加转移的过程中,我们应该看matrix[x][y][0]...matrix[x][y][z]中是否已经有为1的点,如果有就不必再在第z层再走x,y。
我们可以用位运算压缩三维数组,matrix[x][y]第z位代表是否已经遍历过(x,y,z)点。至于判断该点是否可走,我们应该看当前位置(x,y)小于等于z的位是否有1。类似于子网掩码的算法。高于z为置0,低位置1,与matrix[x][y]相与。得到结果大于0则说明有1不需遍历。等于0说明使用更少的飞行器没有走过这一点。可以加入遍历集。
代码:
package main import ( "fmt" ) type Obj struct { X, Y, Z int } func main() { var n, m, sx, ex, sy, ey int var cur byte fmt.Scan(&n, &m) matrix := make([][]int, 0, n) for i := 0; i < n; i++ { matrix = append(matrix, make([]int, m)) for j := 0; j < m + 1; j++ { fmt.Scanf("%c", &cur) switch cur { case 'S': sx = i sy = j case 'E': ex = i ey = j case '#': matrix[i][j] = 1 } } } fmt.Println(bfs(sx,sy, ex, ey, n, m, matrix)) } func bfs(sx, sy, ex, ey, n, m int, matrix [][]int) int { var direction = [][]int{{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, 1}} queue := make([]Obj, 1, m*n) queue[0] = Obj{sx, sy, 0} level := 0 for len(queue) != 0 { level++ for limit := len(queue); limit > 0; limit-- { node := queue[0] queue = queue[1:] direction[4][0], direction[4][1] = n-1-2*node.X, m-1-2*node.Y for _, d := range direction { x, y, z := node.X + d[0], node.Y + d[1], node.Z + d[2] if x == ex && y == ey { return level } if x >= 0 && y >= 0 && x < n && y < n && z <= 5 && ((1<<(z+1))-1) & matrix[x][y] == 0 { matrix[x][y] += 1 << z queue = append(queue, Obj{x, y, z}) } } } } return -1 }
import java.util.*; public class Main { static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, -1}; static int[][][] dp; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String line = scanner.nextLine(); String[] tmp = line.split(" "); int m = Integer.parseInt(tmp[0]); int n = Integer.parseInt(tmp[1]); char[][] map = new char[m][n]; int sx = 0, sy = 0, ex = 0, ey = 0; for (int i = 0; i < m; i++) { line = scanner.nextLine(); for (int j = 0; j < n; j++) { char ch = line.charAt(j); map[i][j] = ch; if (ch == 'S') { sx = i; sy = j; } if (ch == 'E') { ex = i; ey = j; } } } bfs(map, sx, sy, ex, ey); for (int i = 0; i < 6; i++) { if (dp[ex][ey][i] != 0) { System.out.println(dp[ex][ey][i]); return; } } System.out.println(-1); } public static void bfs(char[][] map, int sx, int sy, int ex, int ey) { Deque<int[]> queue = new ArrayDeque<>(); int m = map.length; int n = map[0].length; dp = new int[m][n][6]; queue.offerFirst(new int[] {sx, sy, 0}); while (!queue.isEmpty()) { int[] status = queue.pollLast(); int x = status[0], y = status[1], t = status[2]; int nx = 0, ny = 0, nt = 0; for (int i = 0; i < 5; i++) { if (i == 4) { nx = m - 1 - x; ny = n - 1 - y; nt = t + 1; } else { nx = x + dx[i]; ny = y + dy[i]; nt = t; } if (nx >= 0 && nx < m && ny >= 0 && ny < n && nt < 6 && map[nx][ny] != '#' && dp[nx][ny][nt] == 0) { dp[nx][ny][nt] = dp[x][y][t] + 1; if (nx == ex && ny == ey) { return; } queue.offerFirst(new int[] {nx, ny, nt}); } } } } }
m, n = map(int, input().split()) tag = [[[1]*6 for _ in range(n)] for _ in range(m)] M = [] for i in range(m): row = [_ for _ in input()] M.append(row) for index, r in enumerate(row): if 'S' == r: S = (i, index, 0) if 'E' == r: E = (i, index) def getadj(i, j, z): adjs = [] if z < 5 and m-1-i >= 0 and m-1-i < m and n-1-j>= 0 and n-1-j< n and tag[m-1-i][n-1-j][z+1] and M[m-1-i][n-1-j] != '#': tag[n-1-i][m-1-j][z+1] = 0 adjs.append((n-1-i, m-1-j, z + 1)) if i > 0 and tag[i - 1][j][z] and M[i - 1][j] != '#': tag[i - 1][j][z] = 0 adjs.append((i-1, j, z)) if i + 1 < m and tag[i + 1][j][z] and M[i + 1][j] != '#': tag[i + 1][j][z] = 0 adjs.append((i + 1, j, z)) if j > 0 and tag[i][j - 1][z] and M[i][j - 1] != '#': tag[i][j - 1][z] = 0 adjs.append((i, j - 1, z)) if j + 1 < n and tag[i][j + 1][z] and M[i][j + 1] != '#': tag[i][j + 1][z] = 0 adjs.append((i, j + 1, z)) return adjs s1 = [S] c = 0 #dfs while(s1): s2 = [] for i, j, z in s1: if (i, j) == E: print(c) exit() s2 += getadj(i, j, z) s1 = s2 c += 1 print(-1)
#include <iostream> #include <array> #include <vector> #include <set> using namespace std; /* 看到大家都在把图看成多层图,然后用bfs。然而我比较笨,所以只能把dijkstra改了一下。 模仿dijkstra算法,只不过每个点处维护的不只是一个距离,而是6个, 分别代表到达该点时剩余不低于0,1,2,3,4,5次飞行次数时,所需的最小时间,记作rest_flight[0~5],显然rest_flight是不降的。 首次运行dijkstra算法,不进行任何飞行,只计算出每个点的rest_flight[5]。 第二次运行dijkstra算法,至多进行一次飞行,一个点的rest_flight[4] 1、或者是它的对称点的rest_flight[5]+1 2、或者是已经经过的点集中点的rest_flight[4]+1 ...... 需要注意的是,向周边节点集添加点时,如果可以优化飞点处时间,则要把飞点添加进去,而不能只添加上下左右,因为有些点只能飞到,不能走到。 */ const int BIG = 1e7; class node{ public: bool visited=false; array<int,7> rest_flight{BIG,BIG,BIG,BIG,BIG,BIG,BIG}; enum TYPE { PATH, WALL, START, END } type; node(TYPE t=PATH):type(t){} }; vector<vector<node>> map; int m,n; int start_row,start_col; int end_row,end_col; class pos{ public: int r,c; pos(int row,int col):r(row),c(col){} }; class comp{ public: static int N; bool operator()(const pos &a,const pos &b)const{ if(map[a.r][a.c].rest_flight[N]<map[b.r][b.c].rest_flight[N]) return true; else if(map[a.r][a.c].rest_flight[N]==map[b.r][b.c].rest_flight[N]){ if(a.r<b.r||a.r==b.r&&a.c<b.c) return true; } return false; } }; int comp::N = 0; vector<pos> delta{{-1,0},{1,0},{0,-1},{0,1}}; bool is_valid(const pos &p){ return 0<=p.r&&p.r<n&&0<=p.c&p.c<m&&map[p.r][p.c].type!=node::WALL; } pos mirror(const pos &p){ return {n-1-p.r,m-1-p.c}; } node & getNode(const pos &p){ return map[p.r][p.c]; } void clean_up_visit(){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) map[i][j].visited = false; } void dijkstra(int round){ comp::N = round; set<pos,comp> prior_q; map[start_row][start_col].rest_flight[round] = map[start_row][start_col].rest_flight[round+1] = 0; prior_q.emplace(start_row,start_col); while(!prior_q.empty()){ auto it = prior_q.begin(); if(getNode(*it).visited){ prior_q.erase(it); continue; } getNode(*it).visited = true; if(is_valid(mirror(*it))) { // 如有必要,则添加飞点 node &fly = getNode(mirror(*it)); if(!fly.visited&&fly.rest_flight[round]> getNode(*it).rest_flight[round+1]+1){ fly.rest_flight[round] = getNode(*it).rest_flight[round+1]+1; prior_q.insert(mirror(*it)); } } for(const pos& d:delta){ pos nxt_pos{it->r+d.r,it->c+d.c}; if(!is_valid(nxt_pos)||getNode(nxt_pos).visited) continue; int mn = BIG; if(is_valid(mirror(nxt_pos))) mn = getNode(mirror(nxt_pos)).rest_flight[round + 1] + 1; if(mn > getNode(*it).rest_flight[round] +1) mn = getNode(*it).rest_flight[round] +1; if(mn < getNode(nxt_pos).rest_flight[round]){ getNode(nxt_pos).rest_flight[round]=mn; prior_q.insert(nxt_pos); } } prior_q.erase(it); } } void print(){ for(int i=5;i>=0;i--){ cout<<"round "<<i<<endl; for(int r=0;r<n;r++) { for (int c = 0; c < m; c++) cout << map[r][c].rest_flight[i] << "\t"; cout << endl; } cout<<endl; } } int main() { cin>>n>>m; map.resize(n,vector<node>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ char tmp; cin>>tmp; switch (tmp) { case '#': map[i][j].type = node::WALL; break; case 'S': map[i][j].type = node::START; start_row=i,start_col=j; break; case 'E': map[i][j].type = node::END; end_row=i,end_col=j; break; case '.': map[i][j].type = node::PATH; break; } } for(int i=5;i>=0;i--) { clean_up_visit(); dijkstra(i); } // print(); cout<<((map[end_row][end_col].rest_flight[0]==BIG)?-1:(map[end_row][end_col].rest_flight[0])); } // 64 位输出请用 printf("%lld")
import sys n,m =[int(i) for i in sys.stdin.readline().split()] data = [] for line in sys.stdin: a = list(line.strip("\n")) data.append(a) def bfs(data, start, end,n,m,path): max_op = 5 wait_to_visit = [[0,start[0],start[1],0]] while wait_to_visit: node_cur = wait_to_visit.pop(0) deepth_cur = node_cur[0]; op_cur = node_cur[3] x_cur, y_cur = node_cur[1], node_cur[2] path[x_cur][y_cur] = deepth_cur if op_cur < max_op: x_next = n-1-x_cur; y_next = m-1-y_cur if data[x_next][y_next] == "E": return deepth_cur+1 if data[x_next][y_next] == "." and path[x_next][y_next]<0: wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur+1]) if x_cur-1 > 0: x_next = x_cur-1; y_next = y_cur if data[x_next][y_next] == "E": return deepth_cur+1 if data[x_next][y_next] == "." and path[x_next][y_next]<0: wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur]) if x_cur+1 < n: x_next = x_cur+1; y_next = y_cur if data[x_next][y_next] == "E": return deepth_cur+1 if data[x_next][y_next] == "." and path[x_next][y_next]<0: wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur]) if y_cur-1 > 0: x_next = x_cur; y_next = y_cur-1 if data[x_next][y_next] == "E": return deepth_cur+1 if data[x_next][y_next] == "." and path[x_next][y_next]<0: wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur]) if y_cur+1 < m: x_next = x_cur; y_next = y_cur+1 if data[x_next][y_next] == "E": return deepth_cur+1 if data[x_next][y_next] == "." and path[x_next][y_next]<0: wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur]) #print(wait_to_visit) return -1 def find(data, signal): for i in range(n): for j in range(m): if data[i][j] == signal: return i,j path = [[-1]*m for _ in range(n)] start = find(data, "S") end = find(data, "E") print(bfs(data, start,end,n,m,path))
//感谢楼上的大佬们不吝赐教,学到了很多东西。 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); char[][] board = new char[n][m]; for(int i=0;i<n;i++){ String s = sc.next(); board[i] = s.toCharArray(); } int[][] visited = new int[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(board[i][j]=='S'){ visited[i][j]=1; Node node = new Node(i,j,5,0); System.out.println(bfs(node,board,visited)); } } } } public static int bfs(Node start,char[][] board,int[][] vis){ int n = board.length; int m = board[0].length; //四种走向的表示 int[] dx = {1,-1,0,0}; int[] dy = {0,0,1,-1}; Queue<Node> q = new LinkedList<>(); q.offer(start); while(!q.isEmpty()){ Node node = q.poll(); int x = node.x; int y = node.y; if(board[x][y] == 'E'){ return node.s; } //四个走向+使用飞行器(共五种情况) for(int i=0;i<5;i++){ Node temp = new Node(); if(i==4){ if(node.t>0){ // 这里下标从 0 开始,题目中下标从 1 开始 temp.x = n-1-x; temp.y = n-1-y; temp.t = node.t-1; temp.s = node.s+1; } } else { temp.x = x+dx[i]; temp.y = y+dy[i]; temp.s = node.s+1; temp.t = node.t; } if(check(temp,n,m,board,vis)){ vis[temp.x][temp.y] = 1; q.offer(temp); } } } return -1; } public static boolean check(Node node,int n,int m,char[][] board,int[][] vis){ return node.x>=0&&node.x<n&&node.y>=0&&node.y<m&&board[node.x][node.y]!='#'&&vis[node.x][node.y]==0; } public static class Node{ int x;//坐标x int y;//坐标y int t;//飞行器的个数 int s;//已经走的步数 public Node() { } public Node(int x, int y, int t, int s) { this.x = x; this.y = y; this.t = t; this.s = s; } } }
import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; import java.util.ArrayList; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static List<int []> neighbor(int[][] map, int row, int col, int count){ int n=map.length; int m=map[0].length; List<int[]> list=new ArrayList<>(); if(row+1<n&&map[row+1][col]>0){ list.add(new int[]{row+1, col, count}); } if(col+1<m&&map[row][col+1]>0){ list.add(new int[]{row, col+1, count}); } if(row-1>=0&&map[row-1][col]>0){ list.add(new int[]{row-1, col, count}); } if(col-1>=0&&map[row][col-1]>0){ list.add(new int[]{row, col-1, count}); } if(count>0&&map[n-1-row][m-1-col]>0){ list.add(new int[]{n-1-row, m-1-col, count-1}); } return list; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[][][] visited = new int[n][m][6]; int[][] map=new int[n][m]; int f1=0, f2=0; int row=0, col=0; for(int i=0;i<n;++i){ String s=in.next(); char[] array=s.toCharArray(); for(int j=0;j<m;++j){ if(array[j]=='#'){ map[i][j]=-1; } else if(array[j]=='S'){ map[i][j]=0; row=i; col=j; } else if(array[j]=='.'){ map[i][j]=1; } else{ map[i][j]=2; f1=i; f2=j; } } } visited[row][col][5]=1; int ans = -1; Queue<int[]> queue=new LinkedList<>(); queue.add(new int[]{row,col,5}); outer: while (!queue.isEmpty()) { int sz = queue.size(); for (int i = 0; i < sz; ++i) { int[] cur = queue.poll(); for (int[] mate : neighbor(map, cur[0], cur[1], cur[2])) { if (visited[mate[0]][mate[1]][mate[2]] == 0) { visited[mate[0]][mate[1]][mate[2]] = visited[cur[0]][cur[1]][cur[2]] + 1; if (map[mate[0]][mate[1]] == 2) { break outer; } queue.add(new int[] { mate[0], mate[1], mate[2] }); } } } } for (int i = 0; i < 6; ++i) { if (visited[f1][f2][i]>0) { ans = visited[f1][f2][i]-1; } } System.out.println(ans); } }
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type Node struct { x int y int step int k int } func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) scanner.Scan() n, _ := strconv.Atoi(scanner.Text()) scanner.Scan() m, _ := strconv.Atoi(scanner.Text()) grid := make([][]string, 0) for i := 0; i < n; i++ { scanner.Scan() s := scanner.Text() ss := strings.Split(s, "") grid = append(grid, ss) } start := [2]int{} end := [2]int{} for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == "S" { start[0] = i start[1] = j } else if grid[i][j] == "E" { end[0] = i end[1] = j } } } shortDis(grid, start, end, 5) } func shortDis(grid [][]string, pos, end [2]int, k int) { n := len(grid) m := len(grid[0]) dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} e_k := make([][]int, n) for i := 0; i < n; i++ { e_k[i] = make([]int, m) for j := 0; j < m; j++ { e_k[i][j] = -1 } } start := Node{ x: pos[0], y: pos[1], step: 0, k: k, } q := make([]Node, 0) q = append(q, start) for len(q) != 0 { cur_node := q[0] q = q[1:] if cur_node.x == end[0] && cur_node.y == end[1] { fmt.Println(cur_node.step) return } for i := 0; i < 5; i++ { next_node := Node{ x: 0, y: 0, step: 0, k: 0, } if i < 4 { next_node = Node{ x: cur_node.x + dirs[i][0], y: cur_node.y + dirs[i][1], step: cur_node.step, k: cur_node.k, } } else { next_node = Node{ x: n - cur_node.x - 1, y: m - cur_node.y - 1, step: cur_node.step, k: cur_node.k - 1, } } if !check(grid, next_node, n, m) { continue } if next_node.k > e_k[next_node.x][next_node.y] { next_node.step++ e_k[next_node.x][next_node.y] = next_node.k q = append(q, next_node) } } } fmt.Println(-1) } func check(grid [][]string, node Node, n, m int) bool { if !(0 <= node.x && node.x < n && 0 <= node.y && node.y < m) { return false } if node.k < 0 { return false } if grid[node.x][node.y] == "#" { return false } return true }
#include <iostream> #include <vector> #include <queue> #include <limits.h> using namespace std; struct node { int x; int y; int fly; }; vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int bfs(int x, int y, vector<vector<char>>& map, int n, int m, pair<int, int> end) { queue<node> que; que.push({x, y, 0}); int level = 0; while (!que.empty()) { int size = que.size(); for (int i = 0; i < size; ++i) { node nd = que.front(); que.pop(); x = nd.x; y = nd.y; if (x == end.first && y == end.second) { return level; } for (int j = 0; j < 4; ++j) { //先尝试普通走,尽量不使用飞行器 int nx = x + dir[j][0]; int ny = y + dir[j][1]; if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == '.') { map[nx][ny] = '#'; //已经到访过 que.push({nx, ny, nd.fly}); } } if (nd.fly < 5) { int nx = n - 1 - x; int ny = m - 1 - y; if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == '.') { map[nx][ny] = '#'; que.push({nx, ny, nd.fly + 1}); } } } ++level; } return -1; } int main() { int n, m; cin >> n >> m; pair<int, int> start; pair<int, int> end; vector<vector<char>> map(n, vector<char> (m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> map[i][j]; if (map[i][j] == 'S') { start.first = i; start.second = j; } if (map[i][j] == 'E') { end.first = i; end.second = j; map[i][j] = '.'; } } } cout << bfs(start.first, start.second, map, n, m, end); return 0; }
import java.io.IOException; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); char[][] grid = new char[n][m]; int startX = -1; int startY = -1; int endX = -1; int endY = -1; for (int i = 0; i < n; i++) { String s = scanner.next(); for (int j = 0; j < s.length(); j++) { grid[i][j] = s.charAt(j); if (grid[i][j] == 'S') { startX = i; startY = j; } else if (grid[i][j] == 'E') { endX = i; endY = j; } } } Node node = new Node(startX, startY, 5); Deque<Node> deque = new LinkedList<>(); deque.add(node); boolean[][] vis = new boolean[n][m]; int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; int step = 0; int size = 1; while (!deque.isEmpty()) { int cnt = 0; for (int i = 0; i < size; i++) { Node curr = deque.poll(); // System.out.println(curr.x + " " + curr.y); if (curr.x == endX && curr.y == endY) { System.out.println(step); return; } if (vis[curr.x][curr.y]) { continue; } vis[curr.x][curr.y] = true; for (int j = 0; j < dirs.length; j++) { int nextX = curr.x + dirs[j][0]; int nextY = curr.y + dirs[j][1]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && grid[nextX][nextY] != '#') { deque.add(new Node(nextX, nextY, curr.cnt)); cnt++; } } if (curr.cnt > 0) { int nextX = n - 1 - curr.x; int nextY = m - 1 - curr.y; if (grid[nextX][nextY] != '#') { deque.add(new Node(nextX, nextY, curr.cnt - 1)); cnt++; } } } size = cnt; step++; } System.out.println(-1); } private static class Node { int x; int y; int cnt; public Node(int x, int y, int cnt) { this.x = x; this.y = y; this.cnt = cnt; } } }
''' BFS加记录结点的当前代价以及剩余的转移次数的信息 ''' import queue class Node(): def __init__(self) -> None: self.x = None self.y = None self.c = None self.t = None def check(node): if 0<=node.x<n and 0<=node.y<m and node.t>=0 and vis[node.x][node.y]==0 and Mat[node.x][node.y]!='#': return True return False def BFS(node): Q = queue.Queue() Q.put(node) while Q.qsize(): node = Q.get() if node.x == ex and node.y == ey: return node.c for i in range(5): temp = Node() if i<4: temp.x = node.x+dirs[i][0] temp.y = node.y+dirs[i][1] temp.c = node.c+1 temp.t = node.t else: temp.x = n-1-node.x temp.y = m-1-node.y temp.c = node.c+1 temp.t = node.t-1 if check(temp): vis[temp.x][temp.y]=1 Q.put(temp) return -1 while True: try: dirs = [[0,1],[1,0],[0,-1],[-1,0]] n,m = map(int,input().split()) vis = [[0]*m for _ in range(n)] Mat = [] for i in range(n): Mat.append(list(input())) sx,sy=-1,-1 ex,ey=-1,-1 for i in range(n): for j in range(m): if Mat[i][j] == 'S': sx,sy=i,j if Mat[i][j] == 'E': ex,ey=i,j sn = Node() sn.x,sn.y,sn.t,sn.c=sx,sy,5,0 vis[sn.x][sn.y]=1 print(BFS(sn)) except: break ''' 4 4 #S.. E#.. #... .... '''
// C++, 广度搜索 #include <bits/stdc++.h> using namespace std; int main() { int y = 0, x = 0; // 获取行与列的大小 cin >> y >> x; vector<string> data(y); string s; int idx = 0; // 获取迷宫数据 while(cin >> s) { data[idx] = std::move(s); idx++; } // 广度优先探索, 只将那些新探索到的或者步数变小的位置加入队列 queue<pair<int,int>> q; // 用于和迷宫进行映射, 每一格保存最小步数以及剩余飞行器 // 初始化将每格步数设为INT_MAX, 飞行器为5 vector<vector<pair<int,int>>> step(y, vector<pair<int,int>>(x, {INT_MAX, 5})); // 将玩家当前位置加入队列 // 并且找出目标位置 int tx = 0, ty = 0; for(int i=0; i<y; i++) { for(int k=0; k<x; k++) { // 找到玩家 if(data[i][k] == 'S') { step[i][k] = {0, 5}; q.push({i,k}); } // 找到目标 if(data[i][k] == 'E') { ty = i; tx = k; } } } while(!q.empty()) { // 这里没必要多这一个size和while的, 但是懒得改了... int size = q.size(); while(size > 0) { // 获取当前的位置 int py = q.front().first; int px = q.front().second; q.pop(); // 1. 尝试向上探索: py > 0, 同时上面不是障碍物 if(py > 0 && data[py-1][px] != '#') { // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列 if(step[py][px].first < step[py-1][px].first - 1) { step[py-1][px] = step[py][px]; step[py-1][px].first++; // 加上当前这一步 q.push({py-1, px}); } } // 2. 尝试向下探索 if(py < y - 1 && data[py+1][px] != '#') { // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列 if(step[py][px].first < step[py+1][px].first - 1) { step[py+1][px] = step[py][px]; step[py+1][px].first++; // 加上当前这一步 q.push({py+1, px}); } } // 3. 向左探索 if(px > 0 && data[py][px - 1] != '#') { // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列 if(step[py][px].first < step[py][px-1].first - 1) { step[py][px-1] = step[py][px]; step[py][px-1].first++; // 加上当前这一步 q.push({py, px-1}); } } // 4. 向右 if(px < x - 1 && data[py][px + 1] != '#') { // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列 if(step[py][px].first < step[py][px+1].first - 1) { step[py][px+1] = step[py][px]; step[py][px+1].first++; // 加上当前这一步 q.push({py, px+1}); } } // 5. 飞行, 到达位置:(y-py+1), (x-px+1), 需要条件:1.还有飞行次数, 2. 飞跃目的地不是障碍物 int fy = y-py-1; int fx = x-px-1; if(step[py][px].second > 0 && data[fy][fx] != '#') { // 飞跃后的位置是新位置, 或者步数更小才更新 if(step[py][px].first < step[fy][fx].first - 1) { step[fy][fx] = step[py][px]; step[fy][fx].first++; step[fy][fx].second--; q.push({fy,fx}); } } size--; } } if(step[ty][tx].first == INT_MAX) cout << -1; else cout << step[ty][tx].first; return 0; }