Codeforces - 377A - Maze

Question

题目大意

就是在一个 maze 中，有 empty cell ( . ) 和 wall ( # )，现在要你将 k 个 . 变成 X ，使得其他 . 还能连通。

解析

反过来思考，设 . 的数目为 emptyNum ，直接搜索到任意一条 emptyNum - k 的 . 的连通路径即可，其余的 k 个点就是答案。

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

public class Main {

    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};

    static int n;
    static int m;
    static int k;
    static char[][] G;
    static int emptyNum;
    static int count;
    static boolean isFind;

    static boolean check(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < m;
    }

    static void dfs(int i, int j) {
        if (count == emptyNum - k) { //already find
            isFind = true;
            return;
        }
        count++;
        G[i][j] = '*';
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (check(ni, nj) && G[ni][nj] == '.')
                dfs(ni, nj);
        }
    }

    public static void main(String[] args) {

        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        n = cin.nextInt();
        m = cin.nextInt();
        k = cin.nextInt();
        G = new char[n][m];

        for (int i = 0; i < n; i++) {
            String str = cin.next();
            for (int j = 0; j < m; j++) {
                if (str.charAt(j) == '.')
                    emptyNum++;
                G[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (G[i][j] == '.') {
                    dfs(i, j);
                    if (isFind)
                        break;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (G[i][j] == '.')
                    G[i][j] = 'X';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (G[i][j] == '*')
                    G[i][j] = '.';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.print(G[i][j]);
            }
            out.println();
        }
        out.println();
    }
}