POJ 1321 棋盘问题 (DFS + 回溯)

发表于 更新于 分类于 ， 本文字数： 1.4k 阅读时长 ≈ 2 分钟

传送门：棋盘问题

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案 C。

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个 n*n 的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为 - 1 -1 时表示输入结束。
随后的 n 行描述了棋盘的形状：每行有 n 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目 C （数据保证 $C \le {2^{31}} $）。

Sample Input

1
2
3
4
5
6
7
8
9
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

1
2
2
1

Solution

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int ans;
int n, k;
char mz[10][10];
bool visrow[10], viscol[10];

void dfs(int i, int used)
{
    if(used == k)
    {
        ans++;
        return;
    }
    if(i > n)
        return;


    for(int j=1; j<=n; j++)
    {
        if(mz[i][j] == '#')
        {
            if(!visrow[i] && !viscol[j])
            {
                visrow[i] = true;
                viscol[j] = true;

                dfs(i+1, used+1);

                visrow[i] = false;
                viscol[j] = false;
            }
        }
    }
    dfs(i+1, used);

}

int main()
{
    while(scanf("%d%d", &n, &k) && (~n || ~k))
    {
        ans = 0;
        memset(visrow, false, sizeof(visrow));
        memset(viscol, false, sizeof(viscol));
        memset(mz, '.', sizeof(mz));
        getchar();
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                mz[i][j] = getchar();
            getchar();
        }
        dfs(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}

Note

还是觉得自己太菜了，于是决定刷一遍 kuangbin 带你飞。决心要把每一道题弄会。

上传代码会精简一些，不放头文件堆叠等一些代码。

2018 年 8 月 10 日

于学校