제출 #1057769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057769		12345678	Mecho (IOI09_mecho)	C++17	32 / 100	87 ms	7024 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

const int nx=805;

int n, s, mn[nx][nx], dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0}, dp[nx][nx];
char mp[nx][nx];
pair<int, int> st, tg;
queue<pair<int, int>> q;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cin>>mp[i][j], mn[i][j]=1e9;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='M') st={i, j};
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='H') q.push({i, j}), mn[i][j]=0;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='D') tg={i, j};
    while (!q.empty())
    {
        auto [x, y]=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            int cx=x+dx[i], cy=y+dy[i];
            if (cx<1||cx>n||cy<1||cy>n||mp[cx][cy]=='T'||mp[cx][cy]=='D') continue;
            if (mn[cx][cy]>mn[x][y]+1) mn[cx][cy]=mn[x][y]+1, q.push({cx, cy});
        }
    }
    int l=0, r=2*n;
    while (l<r)
    {
        int md=(l+r+1)/2;
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j]=1e9;
        if (mn[st.first][st.second]<=md)
        {
            r=md-1;
            continue;
        }
        dp[st.first][st.second]=0;
        q.push({st.first, st.second});
        while (!q.empty())
        {
            auto [x, y]=q.front();
            q.pop();
            for (int i=0; i<4; i++)
            {
                int cx=x+dx[i], cy=y+dy[i];
                if (cx<1||cx>n||cy<1||cy>n||mp[cx][cy]=='T'||mp[cx][cy]=='H') continue;
                if (dp[cx][cy]>dp[x][y]+1&&(md+(dp[x][y]+1)/s)<mn[cx][cy]) dp[cx][cy]=dp[x][y]+1, q.push({cx, cy});
            }
        }
        if (dp[tg.first][tg.second]!=1e9) l=md;
        else r=md-1;
    }
    if (l==0) cout<<-1;
    else cout<<l;
}

• Subtask 1: 32 / 100