【題目連結】
ybt 1217:棋盤問題
OpenJudge NOI 2.5 323:棋盤問題
【題目考點】
1. 深搜
【解題思路】
兩個棋子不能放在棋盤中的同一行或者同一列,那麼相當于要放的棋子是車。并且增加了可以擺放位置、以及擺放棋子數量的限制。
每次搜尋做的事情是:在第l行如何擺放棋子。可以選擇不放棋子,或者在這一行中是
#
且該列沒有被占用的位置擺放棋子。每成功擺放一個棋子,則繼續搜尋,在下一行擺放棋子。
如果擺放完了最後一個棋子,那麼擺放方案計數。
剪枝:如果剩下的行數比剩下的棋子少,每行擺一個棋子也不能把棋子放完,就不用再搜尋了。
【題解代碼】
解法1:深搜
#include<bits/stdc++.h>
using namespace std;
int n, k, ct;//ct:方案計數
bool vis[10];//vis[i]:第i列是否占用
char mp[10][10];//地圖
void dfs(int l, int m)//在第l行擺棋子, 還剩m個棋子
{
if(m == 0)//找到解
{
ct++;
return;
}
if(n-l+1 < m)//剪枝:當剩的行比棋子少時,每行擺一個棋子也不能把棋子放完,就沒有可行解了,直接傳回。
return;
dfs(l+1, m);//第l行不放
for(int i = 1; i <= n; ++i)//在第l行第i列放
{
if(vis[i] == false && mp[l][i] == '#')//如果第i列沒被占用,且(l,i)位置可以放棋子
{
vis[i] = true;
dfs(l+1, m-1);//在第l+1行放棋子,棋子數量減1
vis[i] = false;
}
}
}
int main()
{
while(cin >> n >> k)
{
if(n == -1 && k == -1)
break;
memset(vis, 0, sizeof(vis));//變量清空
ct = 0;
for(int i = 1; i <= n; ++i)//輸入地圖
for(int j = 1; j <= n; ++j)
cin >> mp[i][j];
dfs(1, k);
cout << ct << endl;
}
return 0;
}