제출 #1266835

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

tracks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>

const int maxn = 4100;
string g[maxn];
int dist[maxn][maxn];

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

int h, w;
	bool inside(int x, int y) {
	return (x > -1 && x < h && y > -1 && y < w && g[x][y] != '.');
}


int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> h >> w;
    for (int i = 0; i < h; i++) 
        cin >> g[i];
            

    deque<pii> dq;
    dist[0][0] = 1;
    dq.push_front({0, 0});
    int ans = 0;
	while (dq.size()) {
		pair<int, int> c = dq.front();
		dq.pop_front();
		ans = max(ans, dist[c.first][c.second]);

		for (int i = 0; i < 4; i++) {
			int x = c.first + dx[i], y = c.second + dy[i];
			if (inside(x, y) && dist[x][y] == 0) {
				if (g[x][y] == g[c.first][c.second]) {
					dist[x][y] = dist[c.first][c.second];
					dq.push_front({x, y});
				} else {
					dist[x][y] = dist[c.first][c.second] + 1;
					dq.push_back({x, y});
				}
			}
		}
	}


    cout << ans << '\n';
}

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