题目链接:http://lx.lanqiao.cn/problem.page?gpid=T2993
思路很明确的搜索题,对于搜索题只要是主要好了题目要求并且按照题目要求去做就可以;
这个题需要注意的是一些地方的优化,比如开始的时候我们如果走过了,意思就是说已经走完了并且找到了最小的步骤,如果要是继续走就不值得了;
然后还有就是如果已经走完了就走的步数是最小的;
回溯就不多说了老生常谈;
1 #pragma GCC optimize(3) 2 #include<bits/stdc++.h> 3 using namespace std; 4 int sx,sy; 5 int x[20]; 6 int y[20]; 7 bool vis[20];//标记数组 8 int n; 9 int Min=INT_MAX;//哨兵先设最大值 10 void dfs(int sx,int sy,int step,int cnt)//step表示当前的步数,cnt表示计数器 11 { 12 if(step>Min)//如果当前搜索步数已经大于之前的步数,那么就没有意义了 13 { 14 return ; 15 } 16 if(cnt==n)//搜完了所有的点 17 { 18 Min=min(Min,step); 19 } 20 for(register int i=1;i<=n;i++) 21 { 22 if(vis[i]==false)//没走的过点才可以走 23 { 24 step+=(abs(sx-x[i])+abs(sy-y[i]));//步数 25 cnt++;//记录走过的点数 26 vis[i]=true;//记录走过的点 27 dfs(x[i],y[i],step,cnt); 28 //回溯 29 step-=(abs(sx-x[i])+abs(sy-y[i])); 30 cnt--; 31 vis[i]=false; 32 } 33 } 34 } 35 int main() 36 { 37 ios::sync_with_stdio(false); 38 cin>>sx>>sy; 39 cin>>n; 40 for(register int i=1;i<=n;i++) 41 cin>>x[i]>>y[i]; 42 dfs(sx,sy,0,0); 43 cout<<Min<<endl; 44 return 0; 45 }