侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 656 篇文章
  • 累计创建 127 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】棋盘多项式

GabrielxD
2023-04-19 / 0 评论 / 0 点赞 / 40 阅读 / 1,082 字
温馨提示:
本文最后更新于 2023-04-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 棋盘多项式


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

此题,给你棋盘的规模 nn ,以及挖洞情况,求放 kk 个车的方案数( kk00 到最多可放车数)。

输入

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

接下来 nn 行,每行 nn 个用空格隔开的数字 001100 的形状表示洞,11 表示没有洞

输出

若干行,第 ii 行表示放 ii 个车的方案数

样例输入

3
1 0 1
1 1 1
1 0 1

样例输出

7
12
4

数据规模和约定

  • n8n \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, 2) 为当前搜索到的状态的坐标,那么接下来应该搜 {(3,3)(3,5)}{(4,1)(5,5)}\{(3, 3) \sim (3, 5)\} \cup \{(4, 1) \sim (5, 5)\} 也就是图中标记 x 的这片区域,而不仅仅是 u 的右下角 {(4,3)(5,5)}\{(4, 3) \sim (5, 5)\} 这点区域。

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

注意:根据样例判断,题干中说“求放 kk 个车的方案数( kk00 到最多可放车数)”应该是写错了,要输出的是从 11 到做多可放车数到方案数,所以在搜索到过程最好维护一个最多可放车数方便输出时作右边界。

代码

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]);
    }
}
0

评论区