试题 H: 回忆迷宫

时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分

【问题描述】

爱丽丝刚从一处地下迷宫中探险归来，你能根据她对于自己行动路径的回忆，帮她画出迷宫地图吗?

迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步骤，每个移动步骤可能是上下左右四个方向中的一种，表示爱丽丝往这个方向走了一格。你需要根据这些移动步骤给出一个迷宫地图，并满足以下条件:

1、爱丽丝能在迷宫内的某个空地开始，顺利的走完她回忆的所有移动步骤。

2、迷宫内不存在爱丽丝没有走过的空地。

3、迷宫是封闭的，即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处 视为迷宫外，所有不与迷宫外联通的空地都视为是迷宫内。(迷宫地图为四联通，即只有上下左右视为联通)

4、在满足前面三点的前提下，迷宫的墙的数量要尽可能少。

【输入格式】

第一行一个正整数 N，表示爱丽丝回忆的步骤数量。

接下来一行 N 个英文字符，仅包含 UDLR 四种字符，分别表示上(Up)、下(Down)、左(Left)、右(Right)。

【输出格式】

请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行，用字符 ‘*’ 表示墙，用 ‘ ’(空格)表示非墙。

你的输出需要保证以下条件:

1、至少有一行第一个字符为 ‘*’。

2、第一行至少有一个字符为 ‘*’。

3、每一行的最后一个字符为 ‘*’。

4、最后一行至少有一个字符为 ‘*’。

【样例输入】

17
UUUULLLLDDDDRRRRU

【样例输出】

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

【样例说明】

爱丽丝可以把第六行第六个字符作为起点。

外墙墙墙墙墙外

墙内内内内内墙

墙内墙墙墙内墙

墙内墙墙墙内墙

墙内墙墙墙内墙

墙内内内内内墙

外墙墙墙墙墙外

【评测用例规模与约定】

对于所有数据，0 < N ≤ 100.

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 250, M = 130;
    static int n;
    static String str;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static boolean[][] status = new boolean[N][N], status1 = new boolean[N][N];
    static int[][] g = new int[N][N];
    static char[][] gc = new char[N][N];
    static Queue<Node> q;
    static List<List<Character>> res = new ArrayList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer st = new StreamTokenizer(br);

    static class Node {
        int x, y;

        public Node() {}

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void bfs(int x, int y) {
        q = new LinkedList<>();
        q.add(new Node(x, y));
        Node t;
        while (!q.isEmpty()) {
            t = q.poll();
            if (status[t.x][t.y]) {
                continue;
            }
            status[t.x][t.y] = true;
            for (int i = 0; i < dx.length; ++i) {
                x = t.x + dx[i];
                y = t.y + dy[i];
                if (x < 0 || x >= N || y < 0 || y >= N) {
                    continue;
                }
                if (g[x][y] != 1) {
                    g[x][y] = -1;
                } else {
                    q.add(new Node(x, y));
                }
            }
        }
    }

    static void output(char[][] gc, int n, int m) throws IOException {
        char[][] g = new char[n][m];
        copy(gc, g);
        int l = -1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[j][i] == '*') {
                    l = i;
                    break;
                }
            }
            if (l != -1) {
                break;
            }
        }
        int r;
        for (int i = 0; i < n; ++i) {
            r = -1;
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == '*') {
                    r = j;
                    break;
                }
            }
            if (r == -1) {
                continue;
            }
            List<Character> tmp = new ArrayList<>();
            for (int j = l; j < r; ++j) {
                tmp.add(' ');
            }
            for (int j = r; j < m; ++j) {
                tmp.add(g[i][j]);
            }
            res.add(tmp);
        }
        for (int i = 0; i < res.size(); ++i) {
            for (int j = res.get(i).size() - 1; j > -1; --j) {
                if (res.get(i).get(j) == '*') {
                    break;
                }
                res.get(i).remove(j);
            }
        }
        for (int i = 0; i < res.size(); ++i) {
            for (int j = 0; j < res.get(i).size(); ++j) {
                if (res.get(i).get(j) == '*' && !status1[i][j] && dfs(i, j, i, j, 0)) {
                    bfs1(i + 1, j + 1);
                }
            }
        }
        for (int i = 0; i < res.size(); ++i) {
            for (int j = 0; j < res.get(i).size(); ++j) {
                bw.write(res.get(i).get(j));
            }
            bw.write("\n");
        }
    }

    static void copy(char[][] a, char[][] b) {
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; j < a.length; ++j) {
                b[i][j] = a[i][j];
            }
        }
    }

    static boolean dfs(int x, int y, int u, int v, int s) {
        status1[x][y] = true;
        int a, b;
        for (int i = 0; i < dx.length; ++i) {
            a = x + dx[i];
            b = y + dy[i];
            if (a > -1 && a < res.size() && b > -1 && b < res.get(a).size()) {
                if (res.get(a).get(b) == '*' && !status1[a][b] && dfs(a, b, u, v, s + 1)) {
                    return true;
                }
                if (a == u && b == v && s > 1) {
                    return true;
                }
            }
        }
        return false;
    }

    static void bfs1(int x, int y) {
        q = new LinkedList<>();
        q.add(new Node(x, y));
        res.get(x).set(y, '*');
        Node t;
        while (!q.isEmpty()) {
            t = q.poll();
            if (status[t.x][t.y]) {
                continue;
            }
            status[t.x][t.y] = true;
            for (int i = 0; i < dx.length; ++i) {
                x = t.x + dx[i];
                y = t.y + dy[i];
                if (x < 0 || x >= res.size() || y < 0 || y >= res.get(x).size()) {
                    continue;
                }
                if (res.get(x).get(y) == ' ') {
                    res.get(x).set(y, '*');
                    q.add(new Node(x, y));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        st.nextToken();
        n = (int)st.nval;
        str = br.readLine();
        char c;
        int x = M, y = M;
        g[x][y] = 1;
        for (int i = 0; i < str.length(); ++i) {
            c = str.charAt(i);
            switch (c) {
                case 'U':
                    x += dx[0];
                    y += dy[0];
                    break;
                case 'R':
                    x += dx[1];
                    y += dy[1];
                    break;
                case 'D':
                    x += dx[2];
                    y += dy[2];
                    break;
                case 'L':
                    x += dx[3];
                    y += dy[3];
                    break;
                default:
            }
            g[x][y] = 1;
        }
        bfs(M, M);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                gc[i][j] = g[i][j] == -1 ? '*' : ' ';
            }
        }
        output(gc, N, N);
        bw.close();
    }
}