X星球的一处迷宫游乐场建在某个小山坡上。
它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。
我们假设玩家是面朝上坡的方向站立,则:
L表示走到左边的房间,
R表示走到右边的房间,
U表示走到上坡方向的房间,
D表示走到下坡方向的房间。
X星球的居民有点懒,不愿意费力思考。
他们更喜欢玩运气类的游戏。这个游戏也是如此!
开始的时候,直升机把100名玩家放入一个个小房间内。
玩家一定要按照地上的字母移动。
迷宫地图如下:
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
请你计算一下,最后,有多少玩家会走出迷宫?
而不是在里边兜圈子。
请提交该整数,表示走出迷宫的玩家数目,不要填写任何多余的内容。
如果你还没明白游戏规则,可以参看一个简化的4x4迷宫的解说图:
public class Main { static String[] map = new String[10]; static boolean[][] book; static boolean flag; public static void main(String[] args) { map[0] = "UDDLUULRUL"; map[1] = "UURLLLRRRU"; map[2] = "RRUURLDLRD"; map[3] = "RUDDDDUUUU"; map[4] = "URUDLLRRUU"; map[5] = "DURLRLDLRL"; map[6] = "ULLURLLRDU"; map[7] = "RDLULLRDDD"; map[8] = "UUDDUDUDLL"; map[9] = "ULRDLUURRR"; int sum = 0; for (int i = 0; i <= 9; i++) for (int j = 0; j <= 9; j++) { flag = false; book = new boolean[10][10]; dfs(i, j); if (!flag) sum++; } System.out.println(sum); } static void dfs(int x, int y) { if (book[x][y]) { flag = true; return; } book[x][y] = true; switch (map[x].charAt(y)) { case 'U': if (check(x - 1, y)) return; dfs(x - 1, y); break; case 'D': if (check(x + 1, y)) return; dfs(x + 1, y); break; case 'L': if (check(x, y - 1)) return; dfs(x, y - 1); break; case 'R': if (check(x, y + 1)) return; dfs(x, y + 1); break; } } static boolean check(int x, int y) { return x < 0 || x > 9 || y < 0 || y > 9; } }