设为首页 加入收藏

TOP

棋盘问题 POJ - 1321(dfs)
2019-08-14 00:09:07 】 浏览:62
Tags:棋盘 问题 POJ 1321 dfs

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n, k;
const int maxn = 10;
char chess[maxn][maxn];
int vis_y[maxn];        //判断该列是否已经有棋子
int sum;
void dfs(int x, int rem)
{
    if(rem == 0)
    {
        sum++;      //已找到一种方案
        return ;
    }
    for(int i = x; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(chess[i][j] == '#' && !vis_y[j])   //表示未访问过的棋盘区域
            {
                vis_y[j] = 1;
                dfs(i+1, rem-1);
                vis_y[j] = 0;     //无论有没有结果,已经完成一次dfs后要保证能重新再次寻找
            }
        }
    }

}
int main()
{
    while(cin >> n >> k && n != -1 && k != -1)
    {
        sum = 0;
        memset(chess, 0, sizeof(chess));
        memset(vis_y, 0, sizeof(vis_y));
        for(int i = 0; i < n; i++)
            scanf("%s", chess[i]);
        dfs(0, k);
        cout << sum << endl;
    }
}

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇201412-2 Z字形扫描(c语言) 下一篇2019.08.02 云从科技C++后台开发