(IOI) 2009 Day 2 p2 Mecho

https://contest.yandex.com/ioi/contest/1363/problems/F/

BFS + 二分搜答案

注意到二分搜的範圍要夠大喔 (可以想想極端case XD，被這個卡超久的)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

#define F first
#define S second

int mp[806][806];
int bee_dis[806][806];

int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1};

int n,s;
pii st;
pii ed;

int dis[806][806];

bool can(int mid)
{
    queue<pii> que;
    memset(dis,-1,sizeof(dis));
    assert(st != make_pair(0,0));
    if (bee_dis[st.F][st.S] == -1) assert(0);
    if (bee_dis[st.F][st.S] <= mid) return false;
    dis[st.F][st.S] = 0;
    que.push(st);
    while (!que.empty())
    {
        pii p=que.front();
        que.pop();
        //cout << "p = " << p.F << " , " << p.S<<
        for (int i=0;4>i;i++)
        {
            int tx=p.F+dx[i];
            int ty=p.S+dy[i];
            if (make_pair(tx,ty) == ed) return true;
            if (mp[tx][ty] == 0 || dis[tx][ty] != -1) continue;
            if (bee_dis[tx][ty] == -1)
            {
                dis[tx][ty] = dis[p.F][p.S] + 1;
                que.push(make_pair(tx,ty));
            }
            else
            {
                int want_dis = dis[p.F][p.S] + 1;
                int del = 0;
                if (want_dis % s == 0)
                {
                    del = 0;
                }
                if (want_dis/s + del + mid < bee_dis[tx][ty])
                {
                    dis[tx][ty] = want_dis;
                    que.push(make_pair(tx,ty));
                }
            }
        }
    }
    return false;
}

int main ()
{
    cin >> n >> s;
    vector<pii> bees;
    for (int i=1;n>=i;i++)
    {
        string ss;
        cin >>ss;
        for (int j=1;n>=j;j++)
        {
            char c = ss[j-1];
            if (c == 'T') continue;
            if (c == 'G')
            {
                mp[i][j] = 1;
            }
            else if (c == 'M')
            {
                st = make_pair(i,j);
                mp[i][j] = 1;
            }
            else if (c == 'D')
            {
                ed = make_pair(i,j);
                mp[i][j] = 2;
            }
            else if (c == 'H')
            {
                bees.push_back(make_pair(i,j));
                mp[i][j] = 1;
            }
        }
    }
    memset(bee_dis,-1,sizeof(bee_dis));
    queue<pii> que;
    for (pii p:bees)
    {
        que.push(p);
        bee_dis[p.F][p.S] = 0;
    }
    while (!que.empty())
    {
        pii p=que.front();
        que.pop();
        for (int i=0;4>i;i++)
        {
            int tx=p.F+dx[i];
            int ty=p.S+dy[i];
            if (mp[tx][ty] == 1 && bee_dis[tx][ty] == -1)
            {
                que.push(make_pair(tx,ty));
                bee_dis[tx][ty] = bee_dis[p.F][p.S] +1;
            }
        }
    }
    if (!can(0))
    {
        cout << -1 << endl;
        return 0;
    }
    int L=0,R = 650212;
    while (R-L != 1)
    {
        int mid=(L+R)>>1;
        if (can(mid)) L = mid;
        else R = mid;
    }
    //assert(L != 20005);
    //assert(can(L) && !can(L+1));
    cout <<L << endl;
}