Submission #152833

#	Time	Username	Problem	Language	Result	Execution time	Memory
152833		Blagojce	Tracks in the Snow (BOI13_tracks)	C++11	32.19 / 100	2094 ms	454536 KiB

tracks

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;
int const red = 0;
int const green = 1;
int const neu = 2;
int const black = 3;

int n, m;
int a[4003][4003];
bool vis[4003][4003];
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0,  1,-1};
int col;
bool ok(int r, int c, int i){
        if(r + dr[i] < n && r + dr[i] >= 0 && c + dc[i] < m && c + dc[i] >= 0 && !vis[r + dr[i]][c + dc[i]] && (a[r + dr[i]][c + dc[i]] == col || a[r + dr[i]][c + dc[i]] == neu)){
                return true;
        }
        else return false;
}
int cnt = 0;
void floodfill(int r, int c){
        fr(i, 0, 4){
                if(ok(r, c, i)){
                        vis[r + dr[i]][c + dc[i]] = true;
                        a[r + dr[i]][c + dc[i]] = neu;
                        cnt ++;
                        floodfill(r + dr[i],c + dc[i]);
                }
        }
}

int main()
{
        cin >> n >> m;
        int all = n * m;
        fr(i, 0, n){
                fr(j, 0, m){
                        char c;
                        cin >> c;
                        if(c == 'R') a[i][j] = red;
                        else if(c == 'F') a[i][j] = green;
                        else{
                                a[i][j] = black;
                                all --;
                        }
                }
        }
        col = a[0][0];
        int ziv = 0;
        cnt = 0;
        while(cnt != all){
                a[0][0] = col;
                memset(vis, false, sizeof(vis));
                cnt = 1;
                vis[0][0] = true;
                floodfill(0, 0);

                col ^= 1;
                ziv ++;
        }

        cout << ziv << endl;

        return 0;
}

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