迷宫问题-栈

迷宫问题-栈"/>

迷宫问题-栈

前置条件：在H*W的图中，"S"表示起点，“G"表示终点且从邻近它的上下左右点到达它要花费1，”."表示从邻近它的上下左右点到达它要花费1，“#”表示从邻近它的上下左右点到达它的花费未知。

问题：给定S到G的最多花费为T，输出#的最大值，若可为无穷大，则输出-1。

输入：第一行H,W,T；接下来输入H*W的地图
输出：#的最大值

例1输入：

2 3 10
S##
.#G

例1输出：

8

S->.->#->G 有(10-2)/1=8

例2输入：

2 3 10
S##
..G

例2输出：

-1

S->.->.->G 此时#的值无关紧要，因为已经可达，所以#可为无穷大。

import java.util.*;public class Main {static class Pos{int x, y;Pos(int x, int y){this.x = x;this.y = y;}}static boolean[][] isV;static char[][] mt;static int res = 0;static int t;public static void main(String[] args) {int h, w;Stack<Pos> path = new Stack<>();Pos cur = null;Scanner sc = new Scanner(System.in);h = sc.nextInt();w = sc.nextInt();t = sc.nextInt();mt = new char[h][w];isV = new boolean[h][w];for(int i = 0; i < h; ++i){String line = sc.next();for(int j = 0; j < w; ++j){mt[i][j] = line.charAt(j);if(mt[i][j] == 'S'){path.push(cur = new Pos(j, i));isV[i][j] = true;}}}goPath(path, cur, h, w);System.out.println(res);}public static void goPath(Stack<Pos> path, Pos cur, int h, int w){if(mt[cur.y][cur.x] == 'G'){Stack<Pos> clone = (Stack<Pos>)path.clone();int lenA = 0, lenB = 1;while(!clone.isEmpty()){Pos pop = clone.pop();if(mt[pop.y][pop.x] == '#'){++lenA;}else if(mt[pop.y][pop.x] == '.'){++lenB;}}if(lenA == 0){res = -1;}if(res != -1 && (t - lenB) % lenA == 0){res = Math.max((t - lenB) / lenA, res);}return;}if(cur.x - 1 >= 0 && !isV[cur.y][cur.x - 1]){Pos newCur = new Pos(cur.x - 1, cur.y);isV[newCur.y][newCur.x] = true;path.add(newCur);goPath(path, newCur, h, w);path.pop();isV[newCur.y][newCur.x] = false;}if(cur.x + 1 < w && !isV[cur.y][cur.x + 1]){Pos newCur = new Pos(cur.x + 1, cur.y);isV[newCur.y][newCur.x] = true;path.add(newCur);goPath(path, newCur, h, w);path.pop();isV[newCur.y][newCur.x] = false;}if(cur.y - 1 >= 0 && !isV[cur.y - 1][cur.x]){Pos newCur = new Pos(cur.x, cur.y - 1);isV[newCur.y][newCur.x] = true;path.add(newCur);goPath(path, newCur, h, w);path.pop();isV[newCur.y][newCur.x] = false;}if(cur.y + 1 < h && !isV[cur.y + 1][cur.x]){Pos newCur = new Pos(cur.x, cur.y + 1);isV[newCur.y][newCur.x] = true;path.add(newCur);goPath(path, newCur, h, w);path.pop();isV[newCur.y][newCur.x] = false;}}
}