Submission #749049

#	Time	Username	Problem	Language	Result	Execution time	Memory
749049		farica	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	579 ms	43100 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,r=0,f=0;
    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];
            if(grid[i][j]=='R') ++r;
            else if(grid[i][j]=='F') ++f;
        }
    }
    queue<pair<int,int>>q;
    q.push({0, 0});
    bool visited[h][w];
    memset(visited, 0, sizeof visited);
    int ans=0;
    if(r) ++ans;
    if(f) ++ans;
    visited[0][0]=1;
    while(!q.empty()) {
        int x=q.front().first, y=q.front().second;
        q.pop();
        if(grid[x][y]=='R') --r;
        else --f;
        if(x && !visited[x-1][y] && grid[x-1][y]==grid[x][y]) {
            visited[x-1][y]=1;
            q.push({x-1, y});
        }
        if(y && !visited[x][y-1] && grid[x][y-1]==grid[x][y]) {
            visited[x][y-1]=1;
            q.push({x, y-1});
        }
        if(x+1<h && !visited[x+1][y] && grid[x+1][y]==grid[x][y]) {
            visited[x+1][y]=1;
            q.push({x+1, y});
        }
        if(y+1<w && !visited[x][y+1] && grid[x][y+1]==grid[x][y]) {
            visited[x][y+1]=1;
            q.push({x, y+1});
        }
    }
    if(grid[0][0]=='R' && r) ++ans;
    else if(grid[0][0]=='F' && f) ++ans;
    cout << ans << 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: 2.1875 / 70