题意：
一个迷宫，有障碍，罗密欧在走到朱丽叶之前必须走完可走的所有格子，统计有多少种走法，并计算出最少转弯次数。最后输出在最少转弯次数的情况下，输出迷宫，每个格子有一个数值，-1代表障碍，剩下的代表第几步走到该格子。
思路：
回溯法。记录路径。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 using namespace std; 10 11 int n,m,k; 12 int map[105][105]; 13 int path[105*105]; 14 int best[105*105]; 15 16 int dx[]={0,0,1,-1,1,1,-1,-1}; 17 int dy[]={1,-1,0,0,1,-1,-1,1}; 18 int p,q,r,s; 19 int minturn=0x3f3f3f3f; 20 int num=0; 21 22 void backtrack(int x,int y,int cur) 23 { 24 if(cur>=n*m-k) 25 { 26 if(x!= r || y!=s) return; 27 int turn=0; 28 for(int i=2;i<cur;i++) 29 if(path[i]!=path[i-1]) turn++; 30 if(turn<minturn) 31 { 32 memcpy(best,path,sizeof(path)); 33 minturn=turn; 34 num=1; 35 } 36 else if(turn==minturn) num++; 37 return; 38 } 39 for(int i=0;i<8;i++) 40 { 41 int xx=x+dx[i]; 42 int yy=y+dy[i]; 43 if(map[xx][yy]==-1) continue; 44 if(xx<1||xx>n||yy<1||yy>m) continue; 45 path[cur]=i; 46 map[xx][yy]=-1; 47 backtrack(xx,yy,cur+1); 48 map[xx][yy]=0; 49 } 50 } 51 52 void path_solve() 53 { 54 int x=p,y=q; 55 map[p][q]=1; 56 for(int i=1;i<n*m-k;i++) 57 { 58 int xx=x+dx[best[i]]; 59 int yy=y+dy[best[i]]; 60 map[xx][yy]=map[x][y]+1; 61 x=xx; 62 y=yy; 63 } 64 } 65 66 int main() 67 { 68 //freopen("D:\input.txt","r",stdin); 69 scanf("%d%d%d",&n,&m,&k); 70 for(int i=0;i<k;i++) 71 { 72 int x,y; 73 scanf("%d%d",&x,&y); 74 map[x][y]=-1; 75 } 76 scanf("%d%d%d%d",&p,&q,&r,&s); 77 map[p][q]=-1; 78 backtrack(p,q,1); 79 path_solve(); 80 printf("%d %d ",minturn,num); 81 for(int i=1;i<=n;i++) 82 { 83 for(int j=1;j<=m;j++) 84 { 85 if(j!=1) printf(" "); 86 printf("%d",map[i][j]); 87 } 88 printf(" "); 89 } 90 91 }