因为看《算法竞赛入门经典》看到了讲回溯这一章节，就拿了一个搜索题来练练手。这个题用回溯做还比较简单。
主要思路是依次遍历每一个格子，首先看是不是空（#），如果是且与之前的棋子不冲突的话就放一个棋子在这里，记录该棋子所在行号和列号。之后再去寻找下一个能放棋子的位置，直到所有棋子放完可行解数量即+1；遇到没有可放的情况则返回上一层调用（这就是“回溯”）。第一次提交是LTE，分析原因错误出现在我的思路上。我想的是把每个棋子看成不同的，这样求解出答案后再除以所有棋子全排列的情况。以题目给的测试用例说明就是：
4 4 ...# ..#. .#.. #...
在这种情况下答案是1，而不是24，也就是说棋子都是一样的。而我一开始是按照棋子不一样去做，得出结果是24后再除以4！，即24/4!=1。虽然结果正确但由于搜索了太多没用的情况所以超时了。其实要想不重复也很简单，只需要在寻找下一个棋子时让行号从上一个棋子的行号+1开始即可做到不重复。另外在回溯的时候要特别注意修改了的全局变量要及时复原！这是非常容易错的一点！！！！切记！！！！！
下面为代码：
#include<iostream>
using namespace std;
char board[8][8];
int visit[8][2]; //visit[i][0]记录第i个棋子的行号visit[i][1]记录列号
int count;
void search(int cur,int k,int n){
if(cur==k) count++;
else{
for (int i=cur?visit[cur-1][0]+1:0;i<n;i++){//回溯时行号为上一个棋子的行号+1
for (int j=0;j<n;j++){ //如果cur是0，则行号从0开始
if (board[i][j]=='.') continue;
int ok=1;
for (int p=0;p<cur;p++){
if (visit[p][0]==i||visit[p][1]==j){ //检查是否会与前cur个值发生冲突
ok=0;
break;
}
}
if(ok==1){
visit[cur][0]=i;
visit[cur][1]=j;
search(cur+1,k,n);
visit[cur][0]=0; //切记！！！！！！！
visit[cur][1]=0; //将修改过的全局变量修改回来！
}
}
}
}
}
int main(){
int n,k;
while(cin>>n>>k&&n!=-1){
count=0;
memset(board,' ',sizeof(board));
memset(visit,0,sizeof(visit));
for (int i=0;i<n;i++){
cin>>board[i];
}
search(0,k,n);
cout<<count<<endl;
}
return 0;
}