Submission #748661

#	Time	Username	Problem	Language	Result	Execution time	Memory
748661		farica	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2122 ms	715532 KiB

tracks

#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1e9+7;
const int MAX_N = 1e6;
const int MAX_N2 = 1e5;
const int TWO_MOD_INV = 500000004;
const int M = 998244353;

void solve() {
    int h,w;
    cin >> h >> w;
    char grid[h][w];
    for(int i=0; i<h; ++i) {
        string s;
        cin >> s;
        for(int j=0; j<w; ++j) grid[i][j]=s[j];
    }
    int f[h][w], r[h][w];
    memset(f, 0, sizeof f);
    memset(r, 0, sizeof r);
    int F=1, R=1;
    queue<pair<int,int>>q;
    q.push({0,0});
    while(!q.empty()) {
        int curx=q.front().first, cury=q.front().second;
        q.pop();
        if(grid[curx][cury]=='.') continue;
        if(curx && f[curx-1][cury]) f[curx][cury]=f[curx-1][cury];
        else if(cury && f[curx][cury-1]) f[curx][cury]=f[curx][cury-1];
        else if(grid[curx][cury]=='F') {
            f[curx][cury]=F;
            ++F;
        }
        if(curx && r[curx-1][cury]) r[curx][cury]=r[curx-1][cury];
        else if(cury && r[curx][cury-1]) r[curx][cury]=r[curx][cury-1];
        else if(grid[curx][cury]=='R') {
            r[curx][cury]=R;
            ++R;
        }
        if(curx+1<h && ((f[curx][cury] && !f[curx+1][cury]) or (r[curx][cury] && !r[curx+1][cury]))) q.push({curx+1, cury});
        if(cury+1<w && ((f[curx][cury] && !f[curx][cury+1]) or (r[curx][cury] && !r[curx][cury+1]))) q.push({curx, cury+1});
    }
    cout << F+R-2 << endl;
}

signed main()
{

    //freopen("odometer.in","r",stdin);
    //freopen("odometer.out","w",stdout);

    int t=1;
    while(t--) solve();

    return 0;
}

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