简单深搜，题意很简单,”#”代表墙，”.”可以走，”@”代表出发点，问最多能到达的方格的最大面积（不走重复）。 其中DFS内部，开始因为这样的错误找不到问题在哪。。
for(i = 0; i<4; i++){ m += dir[i][0]; n += dir[i][1]; dfs(m,n); }错误原因：应在同一个位置上向下左上右试探，函数调用退栈回到当前位置时，p、q的值已经发生了改变。 修改后AC代码：
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; char map[21][21]; int dir[][2] = {{1,0},{0,-1},{-1,0},{0,1}}; int res,W,H; int dfs(int p,int q){ int i,m,n; //printf("p = %d,q = %d ",p,q); if(p>=0 && q>=0 && p<H && q<W && map[p][q]=='.'){ map[p][q] = '#'; res++; } else //(map[i][j]=='#') return 0; for(i = 0; i<4; i++){ m = p + dir[i][0]; n = q + dir[i][1]; dfs(m,n); } return 0; } int main() { int i,j,p,q; while(scanf("%d%d",&W,&H)!=EOF && W!=0){ res = 0; getchar(); for(i = 0; i<H; i++){ for(j = 0; j<W; j++){ scanf("%c",&map[i][j]); if(map[i][j]=='@'){ p = i; q = j; map[p][q] = '.'; } } getchar(); } dfs(p,q); printf("%d\n",res); }//for i return 0; }一类典型的回溯方法应用问题，转两种高效算法题解（分别用递归、非递归）。 http://blog.csdn.net/hackbuteer1/article/details/6657109
回溯算法的核心思想：但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择 首先写的非递归方法，Time Limited.
#include <iostream> #include <stdio.h> #include <string.h> #include <cmath> using namespace std; int res; int map[22],N; int canPlace(int row){ int i; for(i = 0; i<row; i++) if( (abs(i-row) == abs(map[i]-map[row]))||( map[row] == map[i]) ) //得出正确结果的关键：准确找到规律，验证 return 0; return 1; } void queen(int row){ int i; if(row == N){ res++; } else for(i = 0; i<N; i++){ map[row] = i; if(canPlace(row)){ queen(row+1); //思考（row+1） } } return ; } int main() { int i,j; while(scanf("%d",&N)!=EOF && N!=0){ res = 0; memset(map,0,sizeof(map)); queen(0); printf("%d\n",res); } return 0; }注释处不能用queen(row++)，原因是回溯到该位置时，这样的话row的值已经发生变化，并不是回溯到原状态，此处的问题和上一道题出现的问题类似，以后一定要注意。
非递归代码：
#include <iostream> #include <stdio.h> #include <string.h> #include <cmath> #define INITIAL 10000 using namespace std; int res; int map[22],N; int canPlace(int row,int loc){ int i; for(i = 0; i<row; i++) if( (abs(i-row) == abs(map[i]-loc))||( loc == map[i]) ) return 0; return 1; } void queen(){ int i = 0,j = 0; //当前行，当前列 while(i < N){ while(j < N){ if(canPlace(i,j)){ map[i] = j; //回溯到第一行，仍然无法找到可以放置皇后的位置，则说明已经找到所有的解，程序终止 j = 0; break; } else{ j++; } } if(map[i] == INITIAL){ if( i == 0) //回溯到第一行，仍然无法找到可以放置皇后的位置，则说明已经找到所有的解，程序终止 break; else{ i--; j = map[i]+1; map[i] = INITIAL; continue; } } if(i == N-1){ //最后一行找到了一个皇后位置，说明找到一个结果 res++; //不能在此处结束程序，因为我们要找的是N皇后问题的所有解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。 j = map[i]+1; map[i] = INITIAL; continue; } ++i; } } int main() { int i,j; while(scanf("%d",&N)!=EOF && N!=0){ res = 0; memset(map,INITIAL,sizeof(map)); queen(); printf("%d\n",res); } return 0; }改为非递归方法实现，依然TimeLimited。 百度研究了一下，发现好多人遇到同样的问题，最后选择打表。
#include<stdio.h> int main() { int a[11]={0,1,0,0,2,10,4,40,92,352,724},n; while(scanf("%d",&n)!=EOF&&n) { printf("%d\n",a[n]); } return 0; }不打表貌似只能用位运算。位运算部分过后分专项出来学习。
解数独，值得认真思考，这里附上一个很好的题解。 http://blog.csdn.net/riba2534/article/details/53526709 题解中的代码也是可以AC的。 自己写的非递归代码过了样例，找不到WA的原因，后来发现如果遇到障碍需要回退时，自己的算法完全就是有漏洞的，会无限循环，而样例中是难得顺利的一次过，这是非常巧合的。 后来参考了题解中的代码写了递归的方法，终于AC。
#include <stdio.h> #define MAX 9 int map[MAX+1][MAX+1]; int a[100][2]; int num; int ifOk(int x, int y, int n){ int x1,x3,y1,y3,i,j; for(i = 0; i<MAX; i++) if(map[x][i] == n) return 0; for(i = 0; i<MAX; i++) if(map[i][y] == n) return 0; x1 = x/3*3; x3 = x1+3; y1 = y/3*3; y3 = y1+3; for(i = x1; i<x3; i++) for(j = y1; j<y3; j++) if(map[i][j]==n) return 0; return 1; } void dfs(int step){ int i,j; if(step==num){ //为什么如果在main中输出？位没有数值都是零呢？ for(i = 0; i<MAX; i++){ for(j = 0; j<MAX-1; j++){ printf("%d ",map[i][j]); } printf("%d",map[i][j]); printf("\n"); } return ; } for(j = 1; j<=MAX; j++){ if(ifOk(a[step][0],a[step][1],j)){ map [a[step][0]] [a[step][1]] = j; dfs(step+1); map[a[step][0]] [a[step][1]] = 0; } }//for j return; } int main(){ char ch[2]; int i,j,cas=0; while(scanf("%s",&ch)!=EOF){ num = 0; if(ch[0]!='?') map[0][0] = ch[0]-'0'; else{ a[num][0] = 0; a[num][1] = 0; map[0][0] = 0; num++; } for(i = 1; i<MAX; i++){ scanf("%s",&ch); if(ch[0]!='?') map[0][i] = ch[0]-'0'; else{ a[num][0] = 0; a[num][1] = i; map[0][i] = 0; num++; } } for(i = 1; i<MAX; i++) for(j = 0; j<MAX; j++){ scanf("%s",&ch); if(ch[0]!='?') map[i][j] = ch[0]-'0'; else{ a[num][0] = i; a[num][1] = j; map[i][j] = 0; num++; } } //题目这输出方式很奇怪啊，打比赛让自己想我肯定想不到，还要多做题呀 if(cas++) printf("\n"); dfs(0); }//while return 0; }自己在网上找了一道数独题目改成了要求的格式，也可以给大家验证自己的代码： ? 6 1 ? 3 ? ? 2 ? ? 5 ? ? ? 8 1 ? 7 ? ? ? ? ? 7 ? 3 4 ? ? 9 ? ? 6 3 7 8 ? ? 3 2 7 9 5 ? ? 5 7 ? 3 ? ? 9 ? 2 1 9 ? 7 6 ? ? ? ? 8 ? 2 4 ? ? 7 6 ? 6 4 ? ? 1 ? 2 5 ?
