题意：
给出一个n ∗ m的矩阵，对于矩阵里的点，如果为. ..则表示为障碍物，为数字表示经过这个点花费的力气。每次只能到达和当前点的欧几里得距离不超过r的点。并且在移动过程中力气不可以小于0。问在花费的力气小于s的情况下，从第一个非障碍物走到最后一个非障碍物的最小距离。
思路：
实际上花费的力气最多为25 ∗ 25 ∗ 9，所以对于最短路多开一维，d i s [ x ] [ y ] [ w ]表示走到( x , y )节点，花费的力气为w的最短距离。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int>PII; inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} #define read read() #define debug(x) cout<<#x<<":"<<x<<endl; const int maxn=2e5+7,inf=0x3f3f3f3f; char mp[30][30]; ll n,m,r,s; int sx=-1,sy,ex,ey; int h[30][30],idx; struct node{ int x,y,nx; }edge[maxn]; struct node1{ ll w,x,y; }; void add(int ux,int uy,int vx,int vy){ edge[idx]={vx,vy,h[ux][uy]}; h[ux][uy]=idx++; } double dis[30][30][6500]; bool vis[30][30][6500]; double spfa(){ double ans=1.0*inf; queue<node1>q; q.push({mp[sx][sy]-'0',sx,sy}); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<=s;k++) dis[i][j][k]=1000000000.0; dis[sx][sy][mp[sx][sy]-'0']=0;vis[sx][sy][mp[sx][sy]-'0']=1; while(!q.empty()){ node1 t=q.front();q.pop(); int nowx=t.x,nowy=t.y,noww=t.w; //cout<<nowx<<" "<<nowy<<" "<<noww<<endl; vis[nowx][nowy][noww]=0; if(nowx==ex&&nowy==ey){ ans=min(ans,dis[nowx][nowy][noww]); continue; } for(int i=h[nowx][nowy];~i;i=edge[i].nx){ int nex=edge[i].x,ney=edge[i].y,ned=t.w+mp[nex][ney]-'0'; double sum=sqrt((nex-nowx)*(nex-nowx)+(ney-nowy)*(ney-nowy)); if(ned<=s&&dis[nex][ney][ned]>dis[nowx][nowy][noww]+sum){ dis[nex][ney][ned]=dis[nowx][nowy][noww]+sum; if(!vis[nex][ney][ned]){ vis[nex][ney][ned]=1; q.push({ned,nex,ney}); } } } } // cout<<ans<<" "<<inf<<endl; return ans; } int main(){ memset(h,-1,sizeof h); n=read,m=read,r=read,s=read; ll sum=0; rep(i,1,n) cin>>mp[i]+1; rep(i,1,n) rep(j,1,m){ if(mp[i][j]=='.') continue; if(sx==-1) sx=i,sy=j; ex=i,ey=j; sum+=(mp[i][j]-'0'); } s=min(s,sum);//取最小值 //暴力建图 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) for(int o=1;o<=m;o++){ if(i==k&&j==o) continue; if(mp[i][j]!='.'&&mp[k][o]!='.') if((i-k)*(i-k)+(j-o)*(j-o)<=r*r) add(i,j,k,o); } double ans=spfa(); if(ans==inf) puts("impossible"); else printf("%.6lf\n",ans); return 0; } /* 2 9 3 3 10 4 3 8 6 5 8 6 3 8 7 2 9 7 5 8 8 3 10 7 2 9 9 6 6 8 3 8 9 5 8 9 3 10 8 2 9 10 3 8 10 6 6 10 3 10 9 3 8 11 3 10 10 8 6 10 7 4 9 5 8 10 5 8 11 6 6 11 2 9 11 3 10 11 7 4 11 10 4 11 9 2 10 8 6 11 7 2 10 11 2 11 7 2 11 9 2 11 */
