【DFS】棋盘多项式

题目

八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换，确切说，是进行一些改造。比如现在有一张 $n\times n$ 的棋盘，我们在一些格子上抠几个洞，这些洞自然不能放棋子了，会漏下去的。另外，一个车本来能攻击和它的同行同列。现在，你想想，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。

此题，给你棋盘的规模 $n$ ，以及挖洞情况，求放 $k$ 个车的方案数（ $k$ 从 $0$ 到最多可放车数）。

输入

第一行一个整数n表示棋盘大小。

接下来 $n$ 行，每行 $n$ 个用空格隔开的数字 $0$ 或 $1$ ， $0$ 的形状表示洞， $1$ 表示没有洞

输出

若干行，第 $i$ 行表示放 $i$ 个车的方案数

样例输入

样例输出

7
12
4

数据规模和约定

$n \le 8$

解题

方法一：DFS

思路

与八皇后问题不同，本题中可以放的棋子的数量不是固定的，且“车”的攻击范围收到棋盘中洞洞影响，所以不能只枚举行深搜每一列来做，而是要同时搜索每一行和每一列。

需要注意的是，枚举每一行每一列进行搜索时，下一个状态转移的范围应该和枚举的规则一致，具体来说：以先枚举行再枚举列距离：

o o o o o
o o o o o
o u x x x
x x x x x
x x x x x

如上棋盘，字符 u 所在坐标 $(3, 2)$ 为当前搜索到的状态的坐标，那么接下来应该搜 $\{(3, 3) \sim (3, 5)\} \cup \{(4, 1) \sim (5, 5)\}$ 也就是图中标记 x 的这片区域，而不仅仅是 u 的右下角 $\{(4, 3) \sim (5, 5)\}$ 这点区域。

优化：由于搜索的顺序是先行后列，所以当前坐标的右下角是绝对没有被搜索过的未知区域（更不可能放过棋子了），所以在判断当前坐标能否放下棋子时只需要向左向上迭代，寻找有没有已经放过棋子的地方，直到遇到洞或者棋盘边界为止，没有就说明当前坐标可以放棋子。

注意：根据样例判断，题干中说“求放 $k$ 个车的方案数（ $k$ 从 $0$ 到最多可放车数）”应该是写错了，要输出的是从 $1$ 到做多可放车数到方案数，所以在搜索到过程最好维护一个最多可放车数方便输出时作右边界。

代码

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

public class Main {
    static int n;
    static int[][] g;
    static boolean[][] has;
    static int[] cnts;
    static int mx;

    static boolean check(int x, int y) {
        if (g[x][y] == 0 || has[x][y]) return false;
        for (int i = x - 1; i >= 0 && g[i][y] == 1; --i) {
            if (has[i][y]) return false;
        }
        for (int j = y - 1; j >= 0 && g[x][j] == 1; --j) {
            if (has[x][j]) return false;
        }
        return true;
    }

    static void dfs(int r, int c, int cnt) {
        mx = Math.max(mx, cnt);
        ++cnts[cnt];
        for (int i = r; i < n; ++i) {
            for (int j = (i == r ? c + 1 : 0); j < n; ++j) {
                if (check(i, j)) {
                    has[i][j] = true;
                    dfs(i, j, cnt + 1);
                    has[i][j] = false;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        g = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                in.nextToken(); g[i][j] = (int) in.nval;
            }
        }
        has = new boolean[n][n];
        cnts = new int[n * n];
        dfs(0, 0, 0);
        for (int i = 1; i <= mx; ++i) System.out.println(cnts[i]);
    }
}

目录CONTENT

【DFS】棋盘多项式

题目

解题

方法一：DFS

思路

代码

评论区