POJ-1321碁盤問題(dfs)

8285 ワード

碁盤問題
Descriptions:
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の2つの駒を碁盤の中の同じ行または同じ列に置くことができないことを要求する場合は、所定の形状と大きさの碁盤に対して、k個の駒を置くすべての実行可能な配置スキームCをプログラミングして解いてください.
Input入力には複数のテストデータが含まれています.各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
Outputは、各セットのデータに対して、1行の出力を与え、配置されたシナリオ数Cを出力する(データ保証C<2^31).
Sample Input
2 1 #. .# 4 4 …# …#. .#… #… -1 -1
Sample Output
2 1
タイトルリンク:https://vjudge.net/problem/POJ-1321
問題:
この問題は深く捜す入門問題でしょう、特別な穴は何もなくて、主にこのdfsを熟知しています
ACコード
#include 
using namespace std;
int n,k;
int vis[10];//        
char mp[10][10];//    
int ans;
void dfs(int cur,int num)//cur  ,num        
{
    if(num==k)
        ans++;
    for(int i=cur; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(mp[i][j]=='#' && vis[j]==0)
            {
                vis[j]=1;
                dfs(i+1,num+1);
                vis[j]=0;
            }
        }
    }
}
int main()
{
    while(cin >> n >> k)
    {
        if(n==-1 && k==-1)
            break;
        ans=0;
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin >> mp[i][j];
        dfs(0,0);
        cout << ans << endl;
    }
}