蓝桥杯 回忆迷宫 BFS DFS暴力模拟

⭐ 题目地址


样例输入

17
UUUULLLLDDDDRRRRU

样例输出

 *
*     *
* * *
* * *
* * *
*     

🤠 注意方向：颠倒数组，行下标 是 y，列下标 是 x

import java.util.*;public class Main
{
static int n;static int N = 400;
//	1 表示路，2表示墙，3表示外边的未知领域，默认 0 static int[][] g = new int[N][N];static String s;static HashMap<Character, Integer> map = new HashMap<>();// 偏移量映射static int[] dx = { 0, 0, -1, 1 };static int[] dy = { 1, -1, 0, 0 };static int maxx = 0, minx = 320;static int maxy = 0, miny = 320;static class Pair{int x;int y;public Pair(int x, int y){super();this.x = x;this.y = y;}}public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();s = sc.next();// 方向，最后一步走的方向为 U 为 左，所以 U 映射成向左移一位map.put('U', 2);map.put('D', 3);map.put('L', 1);map.put('R', 0);dfs(150, 150, 0);// 先在大地图中打下迷宫的路和迷宫的墙bfs(0, 0);// 迷宫外的未知领域标记为3
//		System.out.println("bug!");//		最会处理里边的墙中墙就好啦，顺便输出for (int i = minx; i <= maxx; i++){for (int j = miny; j <= maxy; j++){if (g[i][j] == 1 || g[i][j] == 3)// 路和未知领域都 是 空格System.out.print(" ");else{System.out.print("*");// 里边的 0 也是 墙（墙中墙）}}System.out.println();}}//	宽搜 起点 （sx,sy）private static void bfs(int sx, int sy){Pair[] q = new Pair[N * N];int hh = 0;int tt = -1;q[++tt] = new Pair(sx, sy);while (hh <= tt){Pair t = q[hh++];int x = t.x;int y = t.y;for (int i = 0; i < 4; i++){int xx = x + dx[i];int yy = y + dy[i];if (xx >= 0 && xx <= maxx + 50 && yy >= 0 && yy <= maxy + 50 && g[xx][yy] == 0){g[xx][yy] = 3;q[++tt] = new Pair(xx, yy);}}}}//	(x,y)表示的是当前点的坐标，u表示的是下一步的移动方向private static void dfs(int x, int y, int u){g[x][y] = 1;// 先开路
//		除了路周围都是墙for (int i = 0; i < 4; i++){int xx = x + dx[i];int yy = y + dy[i];if (g[xx][yy] != 1)g[xx][yy] = 2;
//			开疆扩土，记录国界minx = Math.min(minx, xx);maxx = Math.max(maxx, xx);miny = Math.min(miny, yy);maxy = Math.max(maxy, yy);}
//		最后一步操作是 n-1，所以 n 是递归终点if (u == n)return;//		移动当前这步int nx = x + dx[map.get(s.charAt(u))];int ny = y + dy[map.get(s.charAt(u))];dfs(nx, ny, u + 1);}
}