Submission #1175771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175771		lnwrice	Mecho (IOI09_mecho)	C++20	6 / 100	1098 ms	30704 KiB

mecho

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <deque>
using namespace std;

#define INT long long
#define MAX_INT 2000000024

string str;
vector<vector<int>> b, bear;
vector<string> arr;
deque<pair<int, int>> q;
int n, m;

int in_map(int x, int y) {
    if(x >= 0 && x < n && y >= 0 && y < n) return 1;
    return 0;
}
void q_add(int x, int y, int t) {
    if(!in_map(x, y)) return;
    if(arr[x][y] != 'G') return;
    if(b[x][y] > t) b[x][y] = t;
    else return;
    q_add(x+1, y, t + m);
    q_add(x-1, y, t + m);
    q_add(x, y+1, t + m);
    q_add(x, y-1, t + m);
}
void run(int x, int y, int t) {
    if(!in_map(x, y)) return;
    if(arr[x][y] != 'G' && arr[x][y] != 'D') return;
    //cout << x << " " << y << endl;
    if(bear[x][y] > t) bear[x][y] = t;
    else return;
    if(bear[x][y] >= b[x][y]) return;
    run(x+1, y, t+1);
    run(x-1, y, t+1);
    run(x, y+1, t+1);
    run(x, y-1, t+1);
}

void show_b() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(b[i][j] == MAX_INT) {
                cout << "-1 ";
                continue;
            }
            cout << b[i][j] << " ";
        }   
        cout << endl;
    }
}
void show_bear() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(bear[i][j] == MAX_INT) {
                cout << "-1 ";
                continue;
            }
            cout << bear[i][j] << " ";
        }   
        cout << endl;
    }
}

void clear_bear() {
    int i, j;
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            bear[i][j] = MAX_INT;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);

    int i, j, k, x, y, tx, ty;
    cin >> n >> m;
    arr.resize(n+2);
    //for(auto& num : arr) num.resize(n+2);
    b.resize(n+2);
    for(auto& num : b) {
        num.resize(n+2);
        for(auto& num2 : num) {
            num2 = MAX_INT;
        }
    }
    bear.resize(n+2);
    for(auto& num : bear) {
        num.resize(n+2);
    }

    /**
    for(i = 1; i <= n; i++) {
        cin >> str;
        for(j = 0; j < n; j++) {
            if(str[j] == 'T') {
                arr[i][j+1] = -1;
            }
            else if(str[j] == 'G') {
                arr[i][j+1] = 1;
            }
            else if(str[j] == 'M') {
                arr[i][j+1] = -MAX_INT;
            }
            else if(str[j] == 'D') {
                arr[i][j+1] = MAX_INT;
            }
            else if(str[j] == 'H') {
                arr[i][j+1] = 0;
            }
        }
    }
    /**/

    for(i = 0; i < n; i++) {
        cin >> arr[i];
        for(j = 0; j < n; j++) {
            if(arr[i][j] == 'H') {
                b[i][j] = 0;
                q_add(i+1, j, 3);
                q_add(i-1, j, 3);
                q_add(i, j+1, 3);
                q_add(i, j-1, 3);
            }
            else if(arr[i][j] == 'M') {
                x = i;
                y = j;
            }
            else if(arr[i][j] == 'D') {
                tx = i;
                ty = j;
            }
        }
    }

    //show_b();
    //return 0;

    for(i = 0; ; i++) {
        clear_bear();
        bear[x][y] = 0;
        run(x+1, y, i * m + 1);
        run(x-1, y, i * m + 1);
        run(x, y+1, i * m + 1);
        run(x, y-1, i * m + 1);
        if(bear[tx][ty] == MAX_INT) {
            break;
        }
    }

    cout << i-1;
    
    return 0;
}

• Subtask 1: 6 / 100