Submission #832140

#	Time	Username	Problem	Language	Result	Execution time	Memory
832140		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1080 ms	104496 KiB

tracks

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
char meadow[4004][4004];
int num[4004][4004] = {0};
int main() {
    int row, column;
    cin >> row >> column;
    for(int i=1; i<=row; i++) {
        for(int j=1; j<=column; j++) {
            cin >> meadow[i][j];
        }
    }
    int animals = 1;
    queue<pair<int,int>>q;
    stack<pair<int,int>>other;
    q.push({1,1});
    num[1][1] = 1;
    while(!q.empty()) {
        int bar = q.front().fi;
        int kol = q.front().se;
        q.pop();
        animals = max(animals, num[bar][kol]);
        //atas
        if(bar-1>=1 && num[bar-1][kol]==0) {
            if(meadow[bar-1][kol] == meadow[bar][kol]) {
                q.push({bar-1,kol});
                num[bar-1][kol] = num[bar][kol];
            } else 
            if(meadow[bar-1][kol] != '.') {
                other.push({bar-1,kol});
                num[bar-1][kol] = num[bar][kol]+1;
            }
        }
        //bawah
        if(bar+1<=row && num[bar+1][kol]==0) {
            if(meadow[bar+1][kol] == meadow[bar][kol]) {
                q.push({bar+1,kol});
                num[bar+1][kol] = num[bar][kol];
            } else
            if(meadow[bar+1][kol] != '.') {
                other.push({bar+1,kol});
                num[bar+1][kol] = num[bar][kol]+1;
            }
        }
        //kiri
        if(kol-1>=1 && num[bar][kol-1]==0) {
            if(meadow[bar][kol-1] == meadow[bar][kol]) {
                q.push({bar,kol-1});
                num[bar][kol-1] = num[bar][kol];
            } else
            if(meadow[bar][kol-1] != '.') {
                other.push({bar,kol-1});
                num[bar][kol-1] = num[bar][kol]+1;
            }
        } 
        //kanan
        if(kol+1<=column && num[bar][kol+1]==0) {
            if(meadow[bar][kol+1] == meadow[bar][kol]) {
                q.push({bar,kol+1});
                num[bar][kol+1] = num[bar][kol];
            } else
            if(meadow[bar][kol+1] != '.') {
                other.push({bar,kol+1});
                num[bar][kol+1] = num[bar][kol]+1;
            }
        }
        if(q.empty()==true) {
            while(!other.empty()) {
                q.push(other.top());
                other.pop();
            }
        }
    }
    cout << animals << endl;
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70