棋盘问题

 棋盘问题

PRoblem Description

Input

Output

Example Input

2 1#..#4 4...#..#..#..#...-1 -1
Example Output
21
Hint
poj1321 有链接提示的题目请先去链接处提交程序，AC后提交到SDUTOJ中，以便查询存档。
Author
深度优先搜索练习think：          感觉有些遗憾，比赛中没有选择这道题。剩余70分钟，卡在了最后一题上，原来以为最后一题简单，没想到比赛结束了也没做写出来。。。。。。          唉！下次要记得，不能总想一个题，可以适度的换换，或许会遇到简单的。          还是说说这题吧，这是一道简单的深度优先搜索的题目，加个模板，就能ac。代码实现：#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;}