Submission #211110

#	Time	Username	Problem	Language	Result	Execution time	Memory
211110		Aldas25	Zoo (COCI19_zoo)	C++14	110 / 110	72 ms	17144 KiB

zoo

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
typedef pair<short, short> pii;
typedef vector<pii> vii;

const int MAXN = 16000100;

int n, m;
char grid[4100][4100];
bool checked[4100][4100];
deque<pii> q;
int d[4100][4100];
int curD = 0;

int main()
{
    FAST_IO;

    //ifstream in ("in.txt");

    cin >> n >> m;
    q.push_front({1,1});
    FOR(i, 1, n) FOR(j, 1, m) cin >> grid[i][j];

    //int cnt = 0;
    while (!q.empty()) {
        //int v = 0;
        while (!q.empty() && (checked[q.front().f][q.front().s] || grid[q.front().f][q.front().s]=='*')) {q.pop_front();}
        if (q.empty()) break;
        //cnt++; //curT++;c
        pii v = q.front(); q.pop_front();
        checked[v.f][v.s] = true;
        curD = d[v.f][v.s];

        if (v.f > 1 && !checked[v.f-1][v.s] && grid[v.f-1][v.s] == grid[v.f][v.s]) {
            d[v.f-1][v.s] = d[v.f][v.s];
            q.push_front({v.f-1, v.s});
        }
        if (v.s > 1 && !checked[v.f][v.s-1] && grid[v.f][v.s-1] == grid[v.f][v.s]) {
            d[v.f][v.s-1] = d[v.f][v.s];
            q.push_front({v.f, v.s-1});
        }
        if (v.f < n && !checked[v.f+1][v.s] && grid[v.f+1][v.s] == grid[v.f][v.s]) {
            d[v.f+1][v.s] = d[v.f][v.s];
            q.push_front({v.f+1, v.s});
        }
        if (v.s < m && !checked[v.f][v.s+1] && grid[v.f][v.s+1] == grid[v.f][v.s]) {
            d[v.f][v.s+1] = d[v.f][v.s];
            q.push_front({v.f, v.s+1});
        }


        if (v.f > 1 && !checked[v.f-1][v.s] && grid[v.f-1][v.s] != grid[v.f][v.s] && grid[v.f-1][v.s] != '*') {
            d[v.f-1][v.s] = d[v.f][v.s]+1;
            q.push_back({v.f-1, v.s});
        }
        if (v.s > 1 && !checked[v.f][v.s-1] && grid[v.f][v.s-1] != grid[v.f][v.s] && grid[v.f][v.s-1] != '*') {
            d[v.f][v.s-1] = d[v.f][v.s]+1;
            q.push_back({v.f, v.s-1});
        }
        if (v.f < n && !checked[v.f+1][v.s] && grid[v.f+1][v.s] != grid[v.f][v.s] && grid[v.f+1][v.s] != '*') {
            d[v.f+1][v.s] = d[v.f][v.s]+1;
            q.push_back({v.f+1, v.s});
        }
        if (v.s < m && !checked[v.f][v.s+1] && grid[v.f][v.s+1] != grid[v.f][v.s] && grid[v.f][v.s+1] != '*') {
            d[v.f][v.s+1] = d[v.f][v.s]+1;
            q.push_back({v.f, v.s+1});
        }

        //cout << " d[("<<v.f << ", " << v.s << ") = " << d[v.f][v.s] << endl;

        //dfs (q.front().f, q.front().s);

    }

   // dfsTree (1, -1);

    cout << curD+1;

    return 0;
}

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