Submission #1046431

#TimeUsernameProblemLanguageResultExecution timeMemory
1046431lozergamMaze (JOI23_ho_t3)C++17
35 / 100
2101 ms242056 KiB
#include <bits/stdc++.h> using namespace std; #define ll int #define pb push_back #define For(i, n) for(int (i) = 0; (i) < (n); (i)++) #define debug(x) cout << #x << " : " << x << endl << flush #define endl '\n' #define sz(x) (ll)x.size() #define arr(x) array<ll, x> #define insert emplace const ll INF = 1e9; vector<vector<bool>> a, vis; arr(2) s, e; ll n, m, k; ll ans; vector<arr(2)> v, g; vector<set<ll>> row, col; ll cnt; inline void bfs() { // debug(cnt); while(!v.empty()) { auto x = v.back(); // debug(x[0]); // debug(x[1]); v.pop_back(); if(x[0] != 1 and !vis[x[0] - 1][x[1]]) { if(a[x[0] - 1][x[1]]) g.pb({x[0] - 1, x[1]}); else { vis[x[0] - 1][x[1]] = 1; v.pb({x[0] - 1, x[1]}); } } if(x[0] != n and !vis[x[0] + 1][x[1]]) { if(a[x[0] + 1][x[1]]) g.pb({x[0] + 1, x[1]}); else { v.pb({x[0] + 1, x[1]}); vis[x[0] + 1][x[1]] = 1; } } if(x[1] != 1 and !vis[x[0]][x[1] - 1]) { if(a[x[0]][x[1] - 1]) g.pb({x[0], x[1] - 1}); else { v.pb({x[0], x[1] - 1}); vis[x[0]][x[1] - 1] = 1; } } if(x[1] != m and !vis[x[0]][x[1] + 1]) { if(a[x[0]][x[1] + 1]) g.pb({x[0], x[1] + 1}); else { v.pb({x[0], x[1] + 1}); vis[x[0]][x[1] + 1] = 1; } } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m >> k; a.resize(n + 1); vis.resize(n + 1); row.resize(n + 1); col.resize(m + 1); For(i, n + 1) { a[i].resize(m + 1, 0); vis[i].resize(m + 1, 0); For(j, m + 1) vis[i][j] = 0; } cin >> s[0] >> s[1]; cin >> e[0] >> e[1]; for(int i = 1;i <= n; i++) for(int j = 1;j <= m; j++) { char c; cin >> c; if(c == '.') a[i][j] = 0; else a[i][j] = 1; row[i].insert(j); col[j].insert(i); } For(i, n + 1) row[i].insert(INF); For(i, m + 1) col[i].insert(INF); v.pb(s); vis[s[0]][s[1]] = 1; // 2 4 2 // 1 1 // 2 4 // .### // ###. while(1) { bfs(); if(vis[e[0]][e[1]]) break; for(auto x : g) { arr(2) r, c; r[0] = max(x[0] - k + 1, 1); r[1] = min(x[0] + k - 1, n); c[0] = max(x[1] - k + 1, 1); c[1] = min(x[1] + k - 1, m); if(e[0] >= r[0] and e[0] <= r[1] and e[1] >= c[0] and e[1] <= c[1]) { cout << ans + 1 << endl; return 0; } // debug(x[0]); // debug(x[1]); // debug(r[0]); // debug(r[1]); // debug(c[0]); // debug(c[1]); // debug(endl); auto it = row[r[0]].lower_bound(c[0]); while((*it) <= c[1]) { if(!vis[r[0]][(*it)]) { vis[r[0]][(*it)] = 1; v.pb({r[0], (*it)}); } row[r[0]].erase(it); it = row[r[0]].lower_bound(c[0]); } it = row[r[1]].lower_bound(c[0]); while((*it) <= c[1]) { if(!vis[r[1]][(*it)]) { vis[r[1]][(*it)] = 1; v.pb({r[1], (*it)}); } row[r[1]].erase(it); it = row[r[1]].lower_bound(c[0]); } it = col[c[0]].lower_bound(r[0]); while((*it) <= r[1]) { if(!vis[(*it)][c[0]]) { vis[(*it)][c[0]] = 1; v.pb({(*it), c[0]}); } col[c[0]].erase(it); it = col[c[0]].lower_bound(r[0]); } it = col[c[1]].lower_bound(r[0]); while((*it) <= r[1]) { if(!vis[(*it)][c[1]]) { vis[(*it)][c[1]] = 1; v.pb({(*it), c[1]}); } col[c[1]].erase(it); it = col[c[1]].lower_bound(r[0]); } v.pb(x); vis[x[0]][x[1]] = 1; } g.clear(); ans++; } cout << ans << endl; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:90:2: note: in expansion of macro 'For'
   90 |  For(i, n + 1)
      |  ^~~
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:96:3: note: in expansion of macro 'For'
   96 |   For(j, m + 1)
      |   ^~~
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:118:2: note: in expansion of macro 'For'
  118 |  For(i, n + 1)
      |  ^~~
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:120:2: note: in expansion of macro 'For'
  120 |  For(i, m + 1)
      |  ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...