过题随笔 | 小心火烛的歪（JAVA）|迭代深搜

import java.util.Scanner;

public class Main {
    static char[][] map = new char[8][8];
    static int[][] fireworks = new int[8][8];
    static char[][][] scheme = new char[8][8][8];
    static int q = 0;
    static int n = 0;
    static int m = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        q = in.nextInt();
        for (int i = 0; i < n; ++i) {
            map[i] = in.next().toCharArray();
        }
        if (ok()) {
            System.out.println(0);
            return;
        }
        for (int qp = 1; qp <= q; ++qp) {
            for (int i = 0; i < n; ++i) {
                scheme[qp][i] = in.next().toCharArray();
            }
        }
        //枚举每种情况，dfs深搜
        for (int depth = 1; depth <= q && !found; ++depth) {
            dfs(0, 0, depth, new String());
        }
        if (!found)
            System.out.println(-1);
    }
    static boolean found = false;
    static boolean[] vis = new boolean[8];
    static void dfs(int curScheme, int curNum, int depth, String ans) {
        if (found) return;
        if (ans.length() > 0 && ans.charAt(ans.length() - 1) - '0' < curScheme) return;
        if (curNum == depth && ok()) {
            System.out.println(curNum);
            System.out.println(ans.trim());
            found = true;
        }
        if (curNum > depth) return;
        for (int i = 1; i <= q; ++i) {
            if (vis[i]) continue;
            if (draw(i) == false) {
                undraw(i);
                continue;
            }
            vis[i] = true;
            dfs(i, curNum + 1, depth, ans + " " + i);
            undraw(i);
            vis[i] = false;
        }
    }
    static boolean draw(int curScheme) {
        boolean res = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (scheme[curScheme][i][j] == '1') {
                    if (map[i][j] == '1') res = false;
                    fireworks[i][j]++;
                }
            }
        }
        return res;
    }
    static void undraw(int curScheme) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (scheme[curScheme][i][j] == '1') {
                    fireworks[i][j]--;
                }
            }
        }
    }
    static boolean ok() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (map[i][j] == '0' && fireworks[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

算是我调了很久的代码了吧，昨天晚上写了两个小时没AC，害的我连胜都断了。我的思路也是枚举每一种情况，然后因为要输出所需计划数最小的方案，我就想到用迭代深搜的方式，一步步调整计划数后然后搜索。

我原本是在draw和undraw里直接调整原始的map的，然后后来发现太乱了，就新开了一个fireworks数组来记录烟花堆放。另外还有一个点，我在draw函数提前return了，导致undraw会把本来没有draw的都给提前擦除。提前return真是个坏习惯。

我得思路应该不是最优的，因为我得迭代深搜会搜索之前依旧搜索过的情况。这里应该还可以使用vis数组进行优化剪枝。