제출 #1254487

#제출 시각아이디문제언어결과실행 시간메모리
1254487satyanshuTracks in the Snow (BOI13_tracks)C++20
0 / 100
671 ms121556 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353; const ll INF = 1e9 + 7; bool is_valid(int x, int y, int n, int m) { return x >= 0 && x < n && y >= 0 && y < m; } void solve() { int H, W; cin >> H >> W; vector<string> a(H); for (int i = 0; i < H; i++) { cin >> a[i]; } deque<pair<int, int>> q; vector<vector<int>>dis(H, vector<int>(W, INF)); int ans = 1; q.push_front({0, 0}); dis[0][0] = 1; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop_front(); int del_x[4] = {-1, 0, 0, 1}; int del_y[4] = {0, -1, 1, 0}; for (int i = 0; i < 4; i++) { int new_x = x + del_x[i]; int new_y = y + del_y[i]; if (is_valid(new_x, new_y, H, W) && a[new_x][new_y] != '.') { if (a[new_x][new_y] == a[x][y] && dis[new_x][new_y] > dis[x][y]) { dis[new_x][new_y] = dis[x][y]; q.push_front({new_x, new_y}); } else if (a[new_x][new_y] != a[x][y] && dis[new_x][new_y] > dis[x][y] + 1) { dis[new_x][new_y] = dis[x][y] + 1; q.push_back({new_x, new_y}); } } } } cout << dis[H - 1][W - 1] + 1<< endl; return; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; t = 1; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...