Submission #1093986

#TimeUsernameProblemLanguageResultExecution timeMemory
1093986AbitoMaze (JOI23_ho_t3)C++17
67 / 100
2064 ms118156 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt //#define int long long #define ll long long typedef unsigned long long ull; using namespace std; const int N=2000,M=2e5; int n,m,k,sx,sy,ex,ey,mvx[]={1,0,-1,0},mvy[]={0,1,0,-1}; vector<vector<int>> dis,p; vector<vector<bool>> vis; vector<vector<char>> a; bool ok(int x,int y){ return x>=1 && x<=n && y>=1 && y<=m && a[x][y]=='.'; } void bfs1(){ deque<pair<int,int>> dq; dq.push_front({sx,sy}); dis[sx][sy]=0; while (!dq.empty()){ int x=dq.front().F,y=dq.front().S; dq.pop_front(); if (vis[x][y]) continue; //cout<<x<<' '<<y<<' '<<dis[x][y]<<endl; vis[x][y]=1; for (int i=0;i<4;i++){ int nx=mvx[i]+x,ny=mvy[i]+y; if (!ok(nx,ny)) continue; if (dis[nx][ny]>dis[x][y]){ dis[nx][ny]=dis[x][y]; dq.push_front({nx,ny}); } } for (int i=max(1,x-k);i<=min(n,x+k);i++){ for (int j=max(1,y-k);j<=min(m,y+k);j++){ if (i==x-k && j==y-k) continue; if (i==x-k && j==y+k) continue; if (i==x+k && j==y-k) continue; if (i==x+k && j==y+k) continue; if (dis[i][j]>dis[x][y]+1){ dis[i][j]=dis[x][y]+1; dq.push_back({i,j}); } } } } return; } void bfs2(){ vector<pair<int,int>> q; dis[sx][sy]=0; vis[sx][sy]=1; q.pb({sx,sy}); for (int t=0;t<INT_MAX;t++){ for (int i=0;i<q.size();i++){ int x=q[i].F,y=q[i].S; dis[x][y]=t; for (int j=0;j<4;j++){ int nx=x+mvx[j],ny=y+mvy[j]; if (vis[nx][ny] || !ok(nx,ny)) continue; dis[nx][ny]=t; vis[nx][ny]=1; q.pb({nx,ny}); } } //for (auto u:q) cout<<u.F<<' '<<u.S<<" "; //cout<<endl; if (vis[ex][ey]) break; for (int i=0;i<=n+5;i++) for (int j=0;j<=m+5;j++) p[i][j]=0; for (int i=0;i<q.size();i++){ int x=q[i].F,y=q[i].S; p[max(1,x-k)][max(1,y-k)]++; p[max(1,x-k)][min(m,y+k)+1]--; p[min(n,x+k)+1][max(1,y-k)]--; p[min(n,x+k)+1][min(m,y+k)+1]++; if (x-k>=1 && y-k>=1){ p[x-k][y-k]--; p[x-k+1][y-k]++; p[x-k][y-k+1]++; p[x-k+1][y-k+1]--; } if (x-k>=1 && y+k<=m){ p[x-k][y+k]--; p[x-k+1][y+k]++; p[x-k][y+k+1]++; p[x-k+1][y+k+1]--; } if (x+k<=n && y-k>=1){ p[x+k][y-k]--; p[x+k+1][y-k]++; p[x+k][y-k+1]++; p[x+k+1][y-k+1]--; } if (x+k<=n && y+k<=m){ p[x+k][y+k]--; p[x+k+1][y+k]++; p[x+k][y+k+1]++; p[x+k+1][y+k+1]--; } } for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1]; if (p[i][j]>0 && !vis[i][j]) q.pb({i,j}),vis[i][j]=1; //cout<<p[i][j]<<' '; }//cout<<endl; }//cout<<endl; } } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n>>m>>k>>sx>>sy>>ex>>ey; for (int i=0;i<=n+5;i++){ p.pb({});dis.pb({});vis.pb({});a.pb({}); for (int j=0;j<=m+5;j++){ p[i].pb(0);dis[i].pb(INT_MAX);vis[i].pb(0);a[i].pb('#'); } } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>a[i][j]; if ((2*k+1)*(2*k+1)<=N) bfs1(); else bfs2(); cout<<dis[ex][ey]<<endl; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void bfs2()':
Main.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i=0;i<q.size();i++){
      |                ~^~~~~~~~~
Main.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int i=0;i<q.size();i++){
      |                ~^~~~~~~~~
#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...