Submission #1089517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089517		Hora000	Zoo (COCI19_zoo)	C++14	110 / 110	42 ms	7260 KiB

zoo

#include<iostream>
#include<vector>
#include<deque>
#include<array>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> a(n + 2);
    string c = "";
    for(int i = 0; i <= m + 1; i++) c += "*";
    a[0] = c; 
    a[n + 1] = c;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = "*" + a[i] + "*";
    }
    vector<vector<int>> b(n + 2, vector<int>(m + 2, -1));
    deque<array<int, 2>> dq;
    b[1][1] = 1;
    int maxi = 1;
    dq.push_back({1, 1});
    vector<array<int, 2>> dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    while(!dq.empty()){
        int x = dq.front()[0];
        int y = dq.front()[1];
        dq.pop_front();
        for(auto d : dir){
            int xd = x + d[0];
            int yd = y + d[1];
            if(b[xd][yd] == -1){
                if(a[x][y] == a[xd][yd]){
                    dq.push_front({xd, yd});
                    b[xd][yd] = b[x][y];
                }
                else if(a[xd][yd] != '*'){
                    dq.push_back({xd, yd});
                    b[xd][yd] = b[x][y] + 1;
                    maxi = b[x][y] + 1;
                }
            }
        }
    }
    cout << maxi << "\n";
}

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