棋盤問題

PRoblem Description

Input

Output

Example Input

2 1#..#4 4...#..#..#..#...-1 -1
Example Output
21
Hint
poj1321 有鏈接提示的題目請先去鏈接處提交程序，AC后提交到SDUTOJ中，以便查詢存檔。
Author
深度優(yōu)先搜索練習(xí)think：          感覺有些遺憾，比賽中沒有選擇這道題。剩余70分鐘，卡在了最后一題上，原來以為最后一題簡單，沒想到比賽結(jié)束了也沒做寫出來。。。。。。          唉！下次要記得，不能總想一個題，可以適度的換換，或許會遇到簡單的。          還是說說這題吧，這是一道簡單的深度優(yōu)先搜索的題目，加個模板，就能ac。代碼實現(xiàn)：#include<stdio.h>#include<string.h>char map[1100][1100];int v[1100];int count, n, k;void dfs(int a, int b){     int i, j;     if(b==k)     {       count++;       return;     }     for(i=a;i<=n-1;i++)     {        for(j=0;j<=n-1;j++)        {          if(map[i][j]=='#'&&!v[j])          {             v[j] = 1;             dfs(i+1, b+1);             v[j] = 0;          }        }     }}int main(){  int i;  while(~scanf("%d %d", &n, &k))  {     if(n==-1&&k==-1)          break;     count = 0;     memset(v, 0, sizeof(v));     for(i=0;i<=n-1;i++)     {          scanf("%s", map[i]);    }     dfs(0, 0);     printf("%d/n", count);  }   return 0;}