http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1269
连着做了三个基本的dfs,终于弄懂了搜索和回溯的过程。
此题要求输出所有路径，首先给每一个点编号0~n+m;则存储时只需存储编号，由编号得到坐标的方式： x = num/m, y = num%m; 由坐标得到编号的方式：num = x*m+y;
注意：本题坐标从（1,1）开始，编号后的坐标从（0,0）开始。
1 #include <stdio.h> 2 #include <string.h> 3 const int Max = 20; 4 int map[Max][Max],vis[Max][Max]; 5 int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};//搜索方向，按题意必须是左上右下的顺序 6 int num[Max*Max],row,col,e_x,e_y,step,flag; 7 8 void dfs(int x, int y) 9 { 10 if(x==e_x-1&&y==e_y-1)//到达终点就输出此时的路径 11 { 12 flag = 1; 13 for (int i = 0; i < step; i++) 14 { 15 int xx = num[i]/col+1; 16 int yy = num[i]%col+1; 17 printf("(%d,%d)->",xx,yy); 18 } 19 printf("(%d,%d) ",e_x,e_y); 20 return ; 21 } 22 for(int i = 0; i < 4; i++) 23 { 24 int xx = x+dir[i][0]; 25 int yy = y+dir[i][1]; 26 if(map[xx][yy] == 1&&xx>=0&&yy>=0&&xx<row&&yy<col&&!vis[xx][yy]) 27 { 28 step++; 29 vis[xx][yy] = 1; 30 num[step] = xx*col+yy; 31 dfs(xx,yy); 32 step--;//回溯时去掉路径中重复的点 33 vis[xx][yy] = 0;//恢复现场 34 } 35 36 } 37 } 38 int main() 39 { 40 int s_x,s_y; 41 flag = 0; 42 step = 0; 43 scanf("%d %d",&row,&col); 44 memset(vis,0,sizeof(vis)); 45 for (int i = 0; i < row; i++) 46 for (int j = 0; j < col; j++) 47 { 48 scanf("%d",&map[i][j]); 49 } 50 scanf("%d %d",&s_x,&s_y); 51 scanf("%d %d",&e_x,&e_y); 52 num[0] = (s_x-1)*col + (s_y-1); 53 vis[s_x-1][s_y-1] = 1; 54 dfs(s_x-1,s_y-1); 55 if (!flag) 56 puts("-1"); 57 return 0; 58 59 }