迷宫问题-栈"/>
迷宫问题-栈
前置条件:在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;}}
}
更多推荐
迷宫问题-栈
发布评论