A-碁盤問題POJ-1321(DFS、八皇后)

所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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
構想:定義dfs中rowは置かれたrow行目、cntはcnt個の駒を置くことを意味し、動的計画の状態定義に類似し、探索中に明確な状態定義(動的計画ではDP配列の各次元の意味、DFSでは各パラメータの意味)があれば、ターンテーブル転移方程式のような再帰的深関数を書くことができる.コードに現れるのは、碁盤全体を循環してマークされていない点を見つけ(各層のマーク点が互いに影響しないため遡及する)、dfs(r+1,cnt+)---->次の行、次の行を実現することである.

#include 
#include 

using namespace std;

int n,k;
int ans = 0;
int vis[10];
char maze[10][10];

int check(int x,int y)
{
    if(maze[x][y] == '#' && vis[y] == 0)
    {
        return 1;
    }
    return 0;
}

void dfs(int row,int cnt)//      
{
       n - 1   ，      、
//    if(row > n)//       ？？
//    {
//        return;//          
//    }
    if(cnt == k)
    {
        ans++;
        return;
    }
    //              。
//    for(int r=row;r<=n-(k-cnt);r++)//       ，      
    for(int r = row; r < n; r ++)
        for(int i = 0; i < n; i++)
        {
            if(check(r,i))//           
            {
                //  x,y          。。。
                vis[i] = 1;//  ，                 
                dfs(r + 1,cnt + 1);
                vis[i] = 0;//  ，      
            }
        }
}

int main()
{
    while(~scanf("%d%d",&n,&k) && n != -1 && k != -1)
    {
        ans = 0;//  ，       。
        memset(vis,0,sizeof(vis));
        for(int i = 0; i < n; i++)
        {
            scanf("%s",maze[i]);//scanf("%c")  
        }
        dfs(0,0);
        printf("%d
",ans);
    }
}

転載先:https://www.cnblogs.com/tomjobs/p/10612577.html