POJ 1321 棋盘问题

题目链接：http://poj.org/problem?id=1321

参考：http://www.cnblogs.com/xinxiangqing/p/4692994.html

简单搜索这个题加上  非常可乐的简单bfs大概拖了两个月了吧。主要还是自己太懒了，懒得思考，觉得一点点难就会很怂很怂。

贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;char board[8][8];
int judge[8];
int sum;
int n,k;
int main(int argc, char const *argv[])
{int dfs(int line,int step);while(cin>>n>>k){sum=0;memset(judge,1,sizeof(judge));if(n==-1&&k==-1)break;for(int i=0;i<n;i++){cin>>board[i];}dfs(0,0);cout<<sum<<endl;}	
}int dfs(int line,int step){if(step==k){sum++;return 0;}for(int j=line;j<n;j++)for(int i=0;i<n;i++){if(board[j][i]=='#'&& judge[i]){judge[i]=0;dfs(j+1,step+1);judge[i]=1;}}
}

dfs 经典三段式，感觉讲的特别好。大概就是看了这个之后才找到了思路？

里面还有bfs的一些。

参考：http://blog.csdn.net/fightforyourdream/article/details/12866861

void dfs(int 当前状态)  {  if(当前状态为边界状态)  {  记录或输出  return;  }  for(i=0;i<n;i++)       //横向遍历解答树所有子节点  {  //扩展出一个子状态。  修改了全局变量  if(子状态满足约束条件)  {  dfs(子状态)  }  恢复全局变量//回溯部分  }  }