Submission #1146042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146042		moaipo	Tracks in the Snow (BOI13_tracks)	C++20	3.85 / 100	192 ms	65360 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> v;
vector<pair<int,int>> mv = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>n>>m;
    v = vector<vector<int>> (n, vector<int>(m));
    auto odw = vector<vector<bool>> (n, vector<bool>(m));

    char c;
    for(int i=0;i<n;i++){
        for (int j = 0; j < m; ++j) {
            cin>>c;
            if(c=='R') v[i][j] = 1;
            else if(c=='F') v[i][j] = -1;
        }
    }

    vector<vector<int>> nq;
    vector<vector<int>> q = {{0,0}}; // x, y
    int maxi = 1;
    while(!q.empty()) {
        for(auto &cur : q) {
            int x = cur[0], y = cur[1], r = v[y][x];
            if(r==0) continue;
            for(auto &cm : mv) {
                int nx = x + cm.first, ny = y + cm.second;
                if(nx<0 || ny<0 || nx>=m || ny>=n) continue;
                if(odw[ny][nx]) continue;
                int nr = v[ny][nx];
                if(nr == -1 * r) {
                    nq.push_back({nx, ny});
                } else if(nr == r) {
                    q.push_back({nx, ny});
                }
                odw[ny][nx] = true;
            }
        }
        maxi++;
        q = nq;
        nq = vector<vector<int>>();
    }

    cout<<maxi<<'\n';
}

/*
 5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

 */

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