Submission #1257369

#TimeUsernameProblemLanguageResultExecution timeMemory
1257369chautanphatZoo (COCI19_zoo)C++20
110 / 110
35 ms1608 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...