Submission #1257369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257369		chautanphat	Zoo (COCI19_zoo)	C++20	110 / 110	35 ms	1608 KiB

zoo

#include<bits/stdc++.h>

using namespace std;

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    string s[n+1];
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] = ' '+s[i];

    queue<pair<int, int>> q1, q2;
    if (s[1][1] == 'B') q1.push({1, 1}); else q2.push({1, 1});

    int ans = 0;
    vector<vector<bool>> vs(n+1, vector<bool> (m+1));
    while (!q1.empty() || !q2.empty())
    {
        ans += !q1.empty();
        while (!q1.empty())
        {
            int x = q1.front().first, y = q1.front().second;
            q1.pop();
            for (int i = 0; i < 4; i++)
            {
                int newX = x+dx[i];
                int newY = y+dy[i];
                if (min(newX, newY) < 1 || newX > n || newY > m || s[newX][newY] == '*' || vs[newX][newY]) continue;
                vs[newX][newY] = 1;
                if (s[newX][newY] == 'B') q1.push({newX, newY}); else q2.push({newX, newY});
            }
        }

        ans += !q2.empty();
        while (!q2.empty())
        {
            int x = q2.front().first, y = q2.front().second;
            q2.pop();
            for (int i = 0; i < 4; i++)
            {
                int newX = x+dx[i];
                int newY = y+dy[i];
                if (min(newX, newY) < 1 || newX > n || newY > m || s[newX][newY] == '*' || vs[newX][newY]) continue;
                vs[newX][newY] = 1;
                if (s[newX][newY] == 'T') q2.push({newX, newY}); else q1.push({newX, newY});
            }
        }
    }

    cout << ans;
    return 0;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65