本文共 2932 字，大约阅读时间需要 9 分钟。
读懂题意就能写了，递归层数最多10，怎么写都能过。
DFS：
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair pii;#define pb(a) push(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}void debug() {#ifdef ONLINE_JUDGE#else freopen("in.txt","r",stdin); //freopen("d:\\out1.txt","w",stdout);#endif}int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}const int maxn=25;int g[maxn][maxn];int dx[]={ 0,0,1,-1};int dy[]={ 1,-1,0,0};int n,m;int res;int dfs(int x,int y,int t){ for(int d=0;d<4;d++) { int nx=x+dx[d],ny=y+dy[d]; if(nx<1||nx>n||ny<1||ny>m||g[nx][ny]==1) continue; for(;;) { if(nx<1||nx>n||ny<1||ny>m) break; if(g[nx][ny]==3) { res=min(res,t); return 0; } if(g[nx][ny]==1) { if(t<10) { g[nx][ny]=0; dfs(nx-dx[d],ny-dy[d],t+1); g[nx][ny]=1; } break; } nx+=dx[d]; ny+=dy[d]; } }}int main(){ while(scanf("%d%d",&m,&n)!=EOF&&n) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&g[i][j]); res=INF; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j]==2) { g[i][j]=0; dfs(i,j,1); } printf("%d\n",res==INF?-1:res); } return 0;}
迭代加深速度会快一点：
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair pii;#define pb(a) push(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}void debug() {#ifdef ONLINE_JUDGE#else freopen("in.txt","r",stdin); //freopen("d:\\out1.txt","w",stdout);#endif}int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}const int maxn=25;int g[maxn][maxn];int dx[]={ 0,0,1,-1};int dy[]={ 1,-1,0,0};int n,m;int dfs(int x,int y,int t,int limit){ for(int d=0;d<4;d++) { int nx=x+dx[d],ny=y+dy[d]; if(nx<1||nx>n||ny<1||ny>m||g[nx][ny]==1) continue; for(;;) { if(nx<1||nx>n||ny<1||ny>m) break; if(g[nx][ny]==3) { return 1; } if(g[nx][ny]==1) { if(t
转载于:https://www.cnblogs.com/BMan/p/3648283.html
