Submission #1026814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026814		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	47.50 / 100	2104 ms	87236 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

int h, w;
char m[4000][4000];
queue<pair<int, int> > q;
int vis[4000][4000];
vector<pair<int, int> > dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int main() {
    cin>>h>>w;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin>>m[i][j];
        }
    }
    int res = 1;
    char animal = m[0][0];
    bool finish = false;
    //animal = 'K';
    //cout<<"animal: "<<animal<<endl;
    while(!finish) {
        q.push({0, 0});
        finish = true;
        while(q.size()) {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            if(vis[y][x] == res || (animal != m[y][x] && m[y][x] != 'A'))
                continue;
            if(m[y][x] != 'A')
                finish = false;
            vis[y][x] = res;
            m[y][x] = 'A';
            //cout<<res<<" "<<y<<" "<<x<<endl;
            for(auto d : dir) {
                int newY = y + d.first;
                int newX = x + d.second;
                if(newY >= 0 && newY < h && newX >= 0 && newX < w && vis[newY][newX] != res)
                    if(m[newY][newX] == animal || m[newY][newX] == 'A')
                        q.push({newY, newX});
            }
        }
        res++;
        if(animal == 'R')
            animal = 'F';
        else
            animal = 'R';
        /*
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++)
                cout<<m[i][j];
            cout<<endl;
        }
        */
    }
    cout<<res - 2<<endl;
    return 0;
}

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