POJ 1321——棋盤問題（DFS）

棋盤問題

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 50420	Accepted: 24427

Description

在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請程式設計求解對于給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C。

Input

輸入含有多組測試資料。 

每組資料的第一行是兩個正整數，n k，用一個空格隔開，表示了将在一個n*n的矩陣内描述棋盤，以及擺放棋子的數目。 n <= 8 , k <= n 

當為-1 -1時表示輸入結束。 

随後的n行描述了棋盤的形狀：每行有n個字元，其中 # 表示棋盤區域， . 表示空白區域（資料保證不出現多餘的空白行或者空白列）。 

Output

對于每一組資料，給出一行輸出，輸出擺放的方案數目C （資料保證C<2^31）。

Sample Input

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

Sample Output

2
1
           

這道題乍一看真的跟N皇後問題很像，也是在棋盤上擺棋子，需要滿足同一行、同一列隻能有一個。

不同的是，棋盤有了限制，不是所有位置都可以放。

一開始我的思路是這樣的，先找到第一個能放棋子的位置，開始進行dfs

用兩個數組line，row分别作為标記，記錄改行或該列有沒有被放棋子。

然後。。中間出了一些錯誤以後。

最後發現每次搜尋要從目前能放位置的下一行開始循環找能放的地方。

這樣才不會重複計算。

調了良久以後，最後寫出來個125ms的。

後經思考（又是看了題解），發現不用記錄每一行的通路與否，每次隻要從下一行開始搜尋就能保證不會有同一行兩個棋子。

此外，每次搜尋分兩種情況，一種是這一行放棋子，另一種是不放。這樣就能得出結果。

此題還可以剪枝，如果剩下的行數比目前棋子數少的話，就return 成功優化到16ms。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <cctype>
#define N 10010
using namespace std;
int n,m,ans;
char M[10][10];
bool row[10];
void dfs(int i,int cnt)
{
    if(i>n&&cnt!=0)return;
    if(cnt>n-i)return ;//剪枝，如果剩餘的棋子比行數多的話return
    if(cnt==0)
    {
        ans++;
        return ;
    }
    for(int j=0;j<n;j++)
    {
        if(row[j]==0&&M[i][j]=='#')
        {
            row[j]=1;
            M[i][j]='&';
            dfs(i+1,cnt-1);
            M[i][j]='#';
            row[j]=0;
        }
    }
    dfs(i+1,cnt);

}
int main()
{
    //freopen("C:\\Users\\CQJ3360\\Desktop\\in.txt","r",stdin);
    while(cin>>n>>m)
    {
        if(n==-1&&m==-1)break;
        cin.get();
        ans=0;
      //  memset(line,0,10);
        memset(row,0,10);
        for(int i=0; i<n; i++)
            cin>>M[i];
        dfs(0,m);
        cout<<ans<<endl;
    }
    return 0;
}