Submission #1108793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108793		monaxia	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1000 ms	176784 KiB

tracks

// credit: bieoiibe
 
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
#define vektor vector
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const ll Mod = 1e9 + 7;

void solve(){
    int n, m, ans = 0;
    cin >> n >> m;

    vector <vector <char>> a(n + 1, vector <char> (m + 1));
    vector <vector <int>> v(n + 1, vector <int> (m + 1, 0)), val(n + 1, vector <int> (m + 1, 0));
    int col[4] = {0, 1, 0, -1}, 
        row[4] = {1, 0, -1, 0};

    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) cin >> a[i][j];
    }

    queue <pair <int, int>> q, w;

    q.push({1, 1});

    v[1][1] = val[1][1] = 1;

    while(!q.empty()){
        int x1 = q.front().fr, y1 = q.front().sc;
        q.pop();

        for(int i = 0; i < 4; i ++){
            int x = x1 + col[i], y = y1 + row[i];
            if(x > n || x < 1 || y > m || y < 1 || a[x][y] == '.' || v[x][y]) continue;

            val[x][y] = val[x1][y1];

            if(a[x][y] != a[x1][y1]) val[x][y] ++, w.push({x, y});
            else v[x][y] = 1, q.push({x, y});
        }

        if(q.empty()){
            // cout << w.size() << "\n";
            while(!q.empty() && v[w.front().fr][w.front().sc]) w.pop();
            if(w.empty()) break;

            v[w.front().fr][w.front().sc] = 1;
            q.push(w.front());
            w.pop();
        }
    }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) ans = max(ans, val[i][j]);

    cout << ans;
} 

 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
 
    if(fopen("blank.inp", "r")){
        freopen("blank.inp", "r", stdin);
        freopen("blank.out", "w", stdout);
    }
    
    // cout << 1; return 0;
 
    ll n = 1;
 
    // cin >> n;

    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen("blank.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen("blank.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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