제출 #1156651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156651		Esgeer	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	618 ms	212956 KiB

tracks

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
 
const int mod = 1e9 + 7;
 
using namespace std;
 
const int N = 2e5+5;
const int inf = 1e12;

void solve() {
    int n, m;
    cin >> n >> m;
    string grid[n];

    F(i, 0, n) cin >> grid[i];

    vvi dist(n, vi(m, inf));

    deque<pii> q;
    q.push_back({0, 0});
    dist[0][0] = 1;

    while(q.size()) {
        pii cur = q.front();
        q.pop_front();

        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};

        F(i, 0, 4) {
            int ny = cur.fi + dy[i];
            int nx = cur.se + dx[i];

            if(ny < 0 || nx < 0 || ny >= n || nx >= m || dist[ny][nx] != inf || grid[ny][nx] == '.') continue;

            if(grid[cur.fi][cur.se] == grid[ny][nx]) {
                dist[ny][nx] = dist[cur.fi][cur.se];
                q.push_front({ny, nx});
            } else {
                dist[ny][nx] = dist[cur.fi][cur.se] + 1;
                q.push_back({ny, nx});
            }
        }
    }

    int ans = 1;
    F(i, 0, n) {
        F(j, 0, m) {
            //cout << (dist[i][j] == inf ? "." : to_string(dist[i][j]));
            if(dist[i][j] != inf) ans = max(ans, dist[i][j]);
        }
        //cout << endl;
    }

    cout << ans << endl;
}
 
int32_t main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    #ifdef Local
        freopen("local.in", "r", stdin);
        freopen("local.out", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

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