深搜+剪枝思路 (时间复杂度还是高但能过)
深搜:用y总 dxdy 偏移法搜索上下左右,不满足边界条件时 return
剪枝:二维数组 st[N][N] 存放之前到达过此位置所需的最短路径,利用 st[x][y] > cnt (此次到达 {x,y} 位置所需的路径) 剪枝
Lucas
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110, M=0x3f3f3f3f;
int a[N][N],st[N][N],n,m;
int ans=M;
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
void recur(int r, int c, int cnt) {
if (r==n && c==m) {
ans=min(ans,cnt);
return;
}
for (int i=0; i<4; i++) {
int x=r+dx[i],y=c+dy[i];
if (r>=1 && c>=1 && x<=n && y<=m && a[x][y]==0 && st[x][y]>cnt) {
st[x][y]=cnt;
recur(x,y,cnt+1);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin>>a[i][j];
st[i][j]=M;
}
}
recur(1,1,0);
cout<<ans<<endl;
return 0;
}