题目里面的每一组是先走K步再开k个锁
我们不妨换一下，先走<=k步，然后后面的每个组先开k个锁再走k步
我们可以发现开完再走，走完再开，每一组都一定能走k步
所以只要在地图里找从起点出发，走<=k步后距离边界最短的点
这个跑一个宽搜就可以了（注意不要跑dfs会tle的）
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <utility> #include <map> #include <stack> #include <set> #include <vector> #include <queue> #include <deque> #include <sstream> #include <bitset> #define x first #define y second #define mp make_pair #define pb push_back #define LL long long #define ld long double #define Pair pair<int,int> #define LOWBIT(x) x & (-x) using namespace std; const int INF=0x7ffffff; int ans=INF; int movee[5][3]; bool visited[848][848]; int r,c,k; int sx,sy; int a[848][848]; char s[1000]; queue<int> q; void bfs(int x,int y,int step) { q.push(x);q.push(y);q.push(0); int cur_ans,cx,cy,cd,xx,yy,dd; visited[x][y]=true; while (!q.empty()) { cx=q.front();q.pop(); cy=q.front();q.pop(); cd=q.front();q.pop(); cur_ans=cx-1; cur_ans=min(cur_ans,cy-1); cur_ans=min(cur_ans,r-cx); cur_ans=min(cur_ans,c-cy); ans=min(ans,cur_ans); if (cd==k) continue; for (int i=1;i<=4;i++) { xx=cx+movee[i][1];yy=cy+movee[i][2]; if (xx<1 || xx>r || yy<1 || yy>c) continue; if (a[xx][yy]==1 || visited[xx][yy]) continue; visited[xx][yy]=true;q.push(xx);q.push(yy);q.push(cd+1); } } } int main () { int i,j; movee[1][1]=1;movee[1][2]=0; movee[2][1]=0;movee[2][2]=1; movee[3][1]=-1;movee[3][2]=0; movee[4][1]=0;movee[4][2]=-1; scanf("%d%d%d",&r,&c,&k); for (i=1;i<=r;i++) { scanf("%s",s); for (j=1;j<=c;j++) { if (s[j-1]=='#') a[i][j]=1; if (s[j-1]=='.') a[i][j]=2; if (s[j-1]=='S') { sx=i;sy=j; a[i][j]=2; } } } bfs(sx,sy,0); int fans=1+(ans+k-1)/k; printf("%d\n",fans); return 0; } 注意：宽搜要在搜到的一刹那把visited置成true，而不是在队列里面弹出的时候改