Submission #916965

#	Time	Username	Problem	Language	Result	Execution time	Memory
916965		vanea	Mecho (IOI09_mecho)	C++14	27 / 100	1096 ms	8028 KiB

mecho

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

const int mxN = 1e3+10;

char matrix[mxN][mxN];
bool vis[mxN][mxN];
int d[mxN][mxN];

int n, s;
pair<int, int> start, finish;

vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};

bool valid(int x, int y, vector<vector<char>> &curr) {
    return (x >= 0 && x < n && y < n && y >= 0 && !vis[x][y] &&
            curr[x][y] == 'G');
}

bool valid1(int x, int y, vector<vector<char>> &curr) {
    return (x >= 0 && x < n && y < n && y >= 0 &&
            (curr[x][y] == 'G' || curr[x][y] == 'D'));
}

bool just[mxN][mxN];

void dfs(vector<vector<char>> &curr, int i, int j) {
    vis[i][j] = true;
    for(int k = 0; k < 4; k++) {
        int a = i+xy[k], b = j+yx[k];
        if(valid(a, b, curr)) {
            curr[a][b] = 'H';
            if(a > i) just[a][b] = true;
            if(a == i && b > j) just[a][b] = true;
        }
    }
}

void exec(vector<vector<char>> &curr) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(curr[i][j] == 'H' && !vis[i][j] && !just[i][j]) {
                dfs(curr, i, j);
            }
            just[i][j] = false;
        }
    }
}

bool f(int mid) {
    memset(vis, false, sizeof vis);
    memset(d, 0x3F, sizeof d);
    vector<vector<char>> curr(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            curr[i].push_back(matrix[i][j]);
        }
    }
    for(int k = 0; k < mid; k++) {
        exec(curr);
    }
    queue<array<int, 3>> q;
    q.push({start.first, start.second, 0});
    d[start.first][start.second] = 0;
    int last = 0;
    while(!q.empty()) {
        auto x = q.front()[0], y = q.front()[1], dist = q.front()[2];
        q.pop();
        if((dist != last) && (last % s == 0) && last) {
            exec(curr);
        }
        last = dist;
        if(curr[x][y] == 'H') continue;
        if(x == finish.first && y == finish.second) {
            return true;
        }
        int new_d = d[x][y] + 1;;
        for(int k = 0; k < 4; k++) {
            int a = x + xy[k], b = y + yx[k];
            if(valid1(a, b, curr) && new_d < d[a][b]) {
                d[a][b] = new_d;
                q.push({a, b, dist+1});
            }
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> matrix[i][j];
            if(matrix[i][j] == 'M') {
                start = {i, j};
                matrix[i][j] = 'G';
            }
            if(matrix[i][j] == 'D') {
                finish = {i, j};
            }
        }
    }
    int l = 0, r = n*n;
    while(l < r) {
        int mid = l + (r - l + 1) / 2;
        if(f(mid)) {
            l = mid;
        }
        else r = mid-1;
    }
    cout << (f(l) ? l : -1);
}

• Subtask 1: 27 / 100