这里详细讲一下剪枝的点:
因为,可以重复在同一个点上走动。所以,这个步数是无穷的。
剪枝一:步数< n*m; (因为起点不算所以不取等号)
剪枝二:步数当大于已有的答案时,直接退出DFS,因为你已经知道这个线路不是答案了,那就没有必要走出去的必要了。(当时,没想到,还傻傻的想了半天)
#include<iostream> #include<algorithm> using namespace std; const int inf = 0x3f3f3f; int xx[] = { 0, 1, -1, 0, 0 }; int yy[] = { 0, 0, 0, 1, -1 }; int f[11][11]; 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 == 0||sum>ans)return; if (x == x2&&y == y2){ ans = min(ans, sum); return; } for (int i = 1; i <= 4; ++i){ int xk = x + xx[i]; int yk = y + yy[i]; if (xk >= 1 && xk <= n&&yk >= 1 && yk <= m && (f[xk][yk] == 4 || f[xk][yk] == 1||f[xk][yk]==3)){ if (k - 1 == 0)return; if (f[xk][yk] == 4){ dfs(xk, yk, 6, sum + 1); } else dfs(xk, yk, k - 1, sum + 1); } } } int main(){ cin >> n >> m; for (int i = 1; i <= n;++i) for (int j = 1; j <= m; ++j) { cin >> f[i][j]; if (f[i][j] == 2){ x1 = i; yk = j; } else if (f[i][j] == 3){ x2 = i; y2 = j; } } dfs(x1, yk, 6, 0); if (ans == inf)cout << -1 << endl; else cout << ans << endl; }