THINK 簡(jiǎn)單明了的DFS 雖然 到 距離結(jié)束只有15分鐘時(shí) 才開(kāi)始敲，但還是在結(jié)束前2分鐘AC了!!!
PRoblem 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）。 Example Input
2 1
.# 4 4 …# ..#. .#..
-1 -1
Example Output
2 1
#include<bits/stdc++.h>using namespace std;char Map[1050][1050];int v[1050];int Count;int n, k;void DFS(int x, int y);int main() { int i; while(cin >> n >> k) { if (n == -1 && k == -1) break; Count = 0; memset(v, 0, sizeof(v)); for (i = 0;i <= n - 1;i ++) { cin >> Map[i]; } DFS(0,0); cout << Count << endl; } return 0; } void DFS(int x, int y) { int i, j; if (y == k) { Count ++; return ; } for (i = x;i <= n - 1;i ++) { for (j = 0;j <= n - 1;j ++) { if (Map[i][j]=='#'&&!v[j]) { v[j] = 1; DFS(i + 1, y + 1); v[j] = 0; } } } }/***************************************************User name: team3Result: AcceptedTake time: 0msTake Memory: 164KBSubmit time: 2017-02-18 11:28:32****************************************************/新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
