Submission #769502

#TimeUsernameProblemLanguageResultExecution timeMemory
769502EllinorTracks in the Snow (BOI13_tracks)C++14
75.94 / 100
2089 ms217932 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = (a); i < (b); i++) typedef long long ll; int H, W; vector<string> grid; vector<vector<bool>> visited; // bitset ? vector<vector<ll>> dp; priority_queue<vector<ll>> q; void dfs(int hat, int wat, ll num) { //cerr << hat << " " << wat << " " << num << "\n"; if (visited[hat][wat]) return; if (grid[hat][wat] == '.') return; visited[hat][wat] = true; dp[hat][wat] = num; char ch = grid[hat][wat]; if (hat + 1 < H) if (grid[hat + 1][wat] == ch) q.push({-num, hat + 1, wat}); if (wat + 1 < W) if (grid[hat][wat + 1] == ch) q.push({-num, hat, wat + 1}); if (hat - 1 >= 0) if (grid[hat - 1][wat] == ch) q.push({-num, hat - 1, wat}); if (wat - 1 >= 0) if (grid[hat][wat - 1] == ch) q.push({-num, hat, wat - 1}); if (hat + 1 < H) if (grid[hat + 1][wat] != ch) q.push({-(num + 1), hat + 1, wat}); if (wat + 1 < W) if (grid[hat][wat + 1] != ch) q.push({-(num + 1), hat, wat + 1}); if (hat - 1 >= 0) if (grid[hat - 1][wat] != ch) q.push({-(num + 1), hat - 1, wat}); if (wat - 1 >= 0) if (grid[hat][wat - 1] != ch) q.push({-(num + 1), hat, wat - 1}); } int32_t main() { cin>>H>>W; grid.assign(H, ""); rep(i,0,H){ cin>>grid[i]; } visited.assign(H, vector<bool>(W, false)); dp.assign(H, vector<ll>(W, 0)); q.push({-1,0,0}); while(!q.empty()) { auto x = q.top(); q.pop(); dfs(x[1], x[2], -(x[0])); } ll ans = 1; rep(i,0,H){ rep(j,0,W){ ans = max(ans, dp[i][j]); //cerr << dp[i][j]<< " "; } //cerr << "\n"; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...