Submission #748979

#	Time	Username	Problem	Language	Result	Execution time	Memory
748979		farica	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2121 ms	735596 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) {
        for(int j=0; j<w; ++j) cin >> grid[i][j];
    }
    int f[h][w], r[h][w], F=0, R=0;
    memset(f, 0, sizeof f);
    memset(r, 0, sizeof r);
    for(int i=0; i<h; ++i) for(int j=0; j<w; ++j) {
        if(grid[i][j]!='F' or f[i][j]) continue;
        queue<pair<int,int>>q;
        q.push({i, j});
        ++F;
        while(!q.empty()) {
            int x=q.front().first, y=q.front().second;
            q.pop();
            f[x][y]=F;
            if(x && grid[x-1][y]!='.' && !f[x-1][y]) q.push({x-1, y});
            if(y && grid[x][y-1]!='.' && !f[x][y-1]) q.push({x, y-1});
            if(x+1<h && grid[x+1][y]!='.' && !f[x+1][y]) q.push({x+1, y});
            if(y+1<w && grid[x][y+1]!='.' && !f[x][y+1]) q.push({x, y+1});
        }
    }
    for(int i=0; i<h; ++i) for(int j=0; j<w; ++j) {
        if(grid[i][j]!='R' or r[i][j]) continue;
        queue<pair<int,int>>q;
        q.push({i, j});
        ++R;
        while(!q.empty()) {
            int x=q.front().first, y=q.front().second;
            q.pop();
            r[x][y]=R;
            if(x && grid[x-1][y]!='.' && !r[x-1][y]) q.push({x-1, y});
            if(y && grid[x][y-1]!='.' && !r[x][y-1]) q.push({x, y-1});
            if(x+1<h && grid[x+1][y]!='.' && !r[x+1][y]) q.push({x+1, y});
            if(y+1<w && grid[x][y+1]!='.' && !r[x][y+1]) q.push({x, y+1});
        }
    }
    cout << F+R << 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