Submission #535596

#	Time	Username	Problem	Language	Result	Execution time	Memory
535596		louiskwok	Mecho (IOI09_mecho)	C++17	39 / 100	1096 ms	9292 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
bool visited[805][805];
int distBee[805][805];
double distBear[805][805];
char g[805][805];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int mxtime;
int main() {
    queue < pair<int,int> > bfs;
    int n,sr,sc,er,ec;
    double s;
    cin >> n >> s;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            cin >> g[i][j];
            if (g[i][j]=='M') sr = i,sc = j;
            else if (g[i][j]=='D') er = i,ec = j;
            else if (g[i][j]=='H') {
                visited[i][j] = true;
                bfs.push({i,j});
            }
        }
    }
    while (!bfs.empty()) {
        int curR = bfs.front().first;
        int curC = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T') continue;
            visited[nr][nc] = true;
            distBee[nr][nc] = distBee[curR][curC]+1;
            mxtime = max(mxtime,distBee[nr][nc]);
            bfs.push({nr,nc});
        }
    }
    for (int i=mxtime+1;i>=0;i--) {
        memset(visited,0,sizeof visited);
        distBear[sr][sc] = i;
        bfs.push({sr,sc});
        while (!bfs.empty()) {
            int curR = bfs.front().first;
            int curC = bfs.front().second;
            bfs.pop();
            for (int i=0;i<4;i++) {
                int nr = curR + dr[i];
                int nc = curC + dc[i];
                if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||distBear[curR][curC]+(double)1/s>=(double)distBee[nr][nc]) continue;
                visited[nr][nc] = true;
                distBear[nr][nc] = distBear[curR][curC]+1/s;
                bfs.push({nr,nc});
            }
        }
        if (visited[er][ec]) return cout << i << endl,0;
    }
    cout << -1 << endl;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:57:27: warning: 'ec' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         if (visited[er][ec]) return cout << i << endl,0;
      |             ~~~~~~~~~~~~~~^
mecho.cpp:57:27: warning: 'er' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 39 / 100