作者： 一字馬胡
轉(zhuǎn)載標(biāo)志 【2017-12-10】
更新日志
| 日期 | 更新內(nèi)容 | 備注 |
|---|---|---|
| 2017-12-10 | 學(xué)習(xí)dfs | 關(guān)于dfs的算法問(wèn)題 |
Description
在一個(gè)給定形狀的棋盤(pán)（形狀可能是不規(guī)則的）上面擺放棋子逐纬，棋子沒(méi)有區(qū)別。要求擺放時(shí)任意的兩個(gè)棋子不能放在棋盤(pán)中的同一行或者同一列胡诗，請(qǐng)編程求解對(duì)于給定形狀和大小的棋盤(pán)，擺放k個(gè)棋子的所有可行的擺放方案C苟穆。
Input
輸入含有多組測(cè)試數(shù)據(jù)妓忍。
每組數(shù)據(jù)的第一行是兩個(gè)正整數(shù)，n k尝苇，用一個(gè)空格隔開(kāi)铛只，表示了將在一個(gè)n*n的矩陣內(nèi)描述棋盤(pán)，以及擺放棋子的數(shù)目糠溜。 n <= 8 , k <= n
當(dāng)為-1 -1時(shí)表示輸入結(jié)束格仲。
隨后的n行描述了棋盤(pán)的形狀：每行有n個(gè)字符，其中 # 表示棋盤(pán)區(qū)域诵冒， . 表示空白區(qū)域（數(shù)據(jù)保證不出現(xiàn)多余的空白行或者空白列）凯肋。
Output
對(duì)于每一組數(shù)據(jù)，給出一行輸出汽馋，輸出擺放的方案數(shù)目C （數(shù)據(jù)保證C<2^31）侮东。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1
Solve
題目描述得很清楚，需要在一個(gè)給定的棋盤(pán)中放置一些棋子豹芯，要求擺放時(shí)任意的兩個(gè)棋子不能放在棋盤(pán)中的同一行或者同一列悄雅，需要注意的一點(diǎn)是，只有標(biāo)記為“#”的位置上才能放置棋子铁蹈，所以在放置棋子之前需要首先判斷該位置是否被標(biāo)記為“#”宽闲，其次需要注意的是，任意兩個(gè)棋子需要錯(cuò)開(kāi)放置握牧，也就是說(shuō)容诬，你要將一顆棋子放置在某個(gè)位置上，你首先要判斷該位置是否標(biāo)記為“#”沿腰，再次需要判斷览徒，在這個(gè)位置上放置上一顆棋子之后，是否滿足需求【要求擺放時(shí)任意的兩個(gè)棋子不能放在棋盤(pán)中的同一行或者同一列】颂龙，只要這兩條標(biāo)準(zhǔn)檢測(cè)通過(guò)习蓬，那么該位置就可以放上一顆棋子，否則就不能放措嵌。
在實(shí)際的解決問(wèn)題上躲叼，使用dfs來(lái)進(jìn)行搜索擺放的策略數(shù)量，選擇行作為遍歷維度企巢，然后對(duì)每一個(gè)位置進(jìn)行上面提到的兩個(gè)要求的檢測(cè)枫慷，如果通過(guò)，那么就放上一顆棋子，否則不能放棋子流礁，具體的實(shí)現(xiàn)代碼見(jiàn)下面的代碼【c++】：
#include<stdio.h>
#include<string.h>
int n,k,vis[15],ans;
char mat[15][15];
//cur : 當(dāng)前檢測(cè)行
//num : 已經(jīng)擺放的棋子數(shù)
void dfs(int cur, int num) {
if(num == k) {
ans ++;
return;
}
for(int i = cur; i < n; i ++)
for(int j = 0; j < n; j ++)
if(mat[i][j] == '#' && ! vis[j]) {
vis[j] = 1;
dfs(i + 1, num + 1);
vis[j] = 0;
}
}
int main() {
while(~ scanf("%d %d%*c", &n, &k) && n != -1 && k != -1) {
memset(vis, 0, sizeof(vis));
int i;
for(i = 0; i < n; i ++)
gets(mat[i]);
ans=0;
dfs(0, 0);
printf("%d\n", ans);
}
return 0;
}
vis數(shù)組用來(lái)記錄某行是否已經(jīng)放過(guò)棋子了涕俗，因?yàn)槿绻承蟹胚^(guò)棋子了，那么該行肯定不能再放棋子了神帅，這里面可能有一個(gè)疑惑再姑，為什么首先將vis[j] = 1 然后再進(jìn)行 vis[j] = 0，這時(shí)候就有需要將一張圖片放出來(lái)了找御，下面展示了這張關(guān)于dfs的神奇而直觀的圖片元镀，對(duì)于有狀態(tài)的dfs需要特別注意，在進(jìn)行回退的時(shí)候需要將狀態(tài)歸位霎桅，否則會(huì)導(dǎo)致結(jié)果不在預(yù)料之內(nèi)栖疑，只要看懂了下面這張圖，對(duì)dfs也算是有一定的見(jiàn)解了滔驶。
