ABC020C 的题解

osfly · 2023-07-06 21:30:42 · 题解

本题二分 + 搜索。

我们可以先二分出 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;
}