本题二分 + 搜索。
我们可以先二分出 \(x\) 可能的值，再用搜索检验这个答案是否满足要求。若满足，左端点右移，否则右端点左移。
至于搜索可以用记搜加速。
注意输出要换行，否则会 WA。
#include<cstdio>
#include<cstring>
int n,m,t;
char map[20][20];
int sx,sy;
int ex,ey;
long long dp[20][20];//dp[i][j] 表示从起点到 (i,j) 的最短距离
int l,r,mid;
int nxtx[4]={0,0,1,-1};
int nxty[4]={1,-1,0,0};
int ans;
void dfs(int x,int y,long long dis)
{
if(dis>=dp[x][y]) return ;
dp[x][y]=dis;
// printf(".%d %d\n",x,y);
if(x==ex&&y==ey)
{
// printf("!%d\n",dp[x][y]);
return ;
}
for(int i=0;i<4;i++)
{
int nx=x+nxtx[i];
int ny=y+nxty[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
dfs(nx,ny,dis+(map[nx][ny]=='.'?1:mid));
}
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf(" %c",&map[i][j]);
if(map[i][j]=='S') sx=i,sy=j,map[i][j]='.';
if(map[i][j]=='G') ex=i,ey=j,map[i][j]='.';//注意起点和终点都是白格
}
l=1,r=t;//二分，常规操作
while(l<=r)
{
memset(dp,0x3f,sizeof(dp));//记得初始化
mid=(l+r)>>1;
// printf("%d\n",mid);
dfs(sx,sy,0);
if(dp[ex][ey]<=t) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);//注意换行
return 0;
}