首页 kuangbin带你飞

题目描述

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

输入描述:

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

输出描述:

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

输入样例:

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

输出样例:

2
1
ac代码(纯净源码)

注意:vjudge不支持万能头文件

#include <bits/stdc++.h>
using namespace std;

int n, k;
int a[10][10];
int b[10];
int cnt;

bool check(int x, int y) {
    if (a[x][y] == 1 && b[y] == 0) {
        return true;
    } else {
        return false;
    }
}

void DFS(int x, int y) {
    if (y == 0) {
        cnt++;
        return;
    }
    else {
        for (int i = x; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (check(i, j)) {
                    b[j] = 1;
                    DFS(i + 1, y - 1);
                    b[j] = 0;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (cin >> n >> k) {
        if (n == -1 && k == -1) break;
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        cnt = 0;
        for (int i = 0; i < n; ++i) 
        {
            string s;
            cin >> s;
            for (int j = 0; j < n; ++j) {
                if (s[j] == '#') a[i][j] = 1;
            }
        }
        DFS(0, k);
        cout << cnt << endl;
    }
    return 0;
}
心得:
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iomanip>
#include <complex>
#include <cassert>
#include <sstream>
#include <fstream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <valarray>
using namespace std;

int n, k; // n为当前矩阵大小,k为棋子数
int a[10][10]; // 最大矩阵所占据的物理空间 .0 #1
int b[10]; // 判断某列是否有棋子
int cnt; // 方案数目

bool check(int x, int y) { // 判断某个点能否落子
    if (a[x][y] == 1 && b[y] == 0) { // 该点是棋盘区域,且该列可用。
                                     // 注意后一个中括号中为y(判断某列不是某行)
        return true;
    } else {
        return false;
    }
}

void DFS(int x, int y) { // x为当前的行数,y为剩余的棋子
    if (y == 0) { // 不剩棋子的时候直接结束搜素,并且方案数加一
        cnt++;
        return;
    }
    else {
        for (int i = x; i < n; ++i) {
            for (int j = 0; j < n; ++j) { // 从该行开始遍历
                if (check(i, j)) { // 可以当棋子
                    b[j] = 1; // 当棋子
                    DFS(i + 1, y - 1);
                    b[j] = 0; // 不当棋子
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (cin >> n >> k) {
        if (n == -1 && k == -1) break;
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        cnt = 0;
        for (int i = 0; i < n; ++i) 
        {
            string s;
            cin >> s;
            for (int j = 0; j < n; ++j) {
                if (s[j] == '#') a[i][j] = 1;
            }
        }
        DFS(0, k);
        cout << cnt << endl;
    }
    return 0;
}

https://vjudge.net/problem/POJ-1321




文章评论

目录