P2802 回家 (DFS+剪枝)

这里详细讲一下剪枝的点:

  因为,可以重复在同一个点上走动。所以,这个步数是无穷的。

  剪枝一:步数< n*m;    (因为起点不算所以不取等号)

  剪枝二:步数当大于已有的答案时,直接退出DFS,因为你已经知道这个线路不是答案了,那就没有必要走出去的必要了。(当时,没想到,还傻傻的想了半天)

#include<iostream>
#include<algorithm>
using namespace std; const int inf = 0x3f3f3f;
int xx[] = { , , -, , };
int yy[] = { , , , , - };
int f[][];
int n, m, ans=inf, x1, yk, x2, y2; void dfs(int x, int y, int k, int sum){
if (sum >= n*m)return;
if (k == ||sum>ans)return;
if (x == x2&&y == y2){ ans = min(ans, sum); return; }
for (int i = ; i <= ; ++i){
int xk = x + xx[i];
int yk = y + yy[i];
if (xk >= && xk <= n&&yk >= && yk <= m && (f[xk][yk] == || f[xk][yk] == ||f[xk][yk]==)){
if (k - == )return;
if (f[xk][yk] == ){ dfs(xk, yk, , sum + ); }
else dfs(xk, yk, k - , sum + );
}
} } int main(){
cin >> n >> m;
for (int i = ; i <= n;++i)
for (int j = ; j <= m; ++j)
{
cin >> f[i][j];
if (f[i][j] == ){ x1 = i; yk = j; }
else if (f[i][j] == ){ x2 = i; y2 = j; }
}
dfs(x1, yk, , );
if (ans == inf)cout << - << endl;
else cout << ans << endl;
}
上一篇:[转]MVVM架构~mvc,mvp,mvvm大话开篇


下一篇:nant build