제출 #1093729

#제출 시각아이디문제언어결과실행 시간메모리
1093729AbitoMaze (JOI23_ho_t3)C++17
19 / 100
2098 ms10076 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=400,M=2e5; int dis[N][M],n,m,k,p[N][M],sx,sy,ex,ey,mvx[]={1,0,-1,0},mvy[]={0,1,0,-1}; char a[N][M]; bool vis[N][M]; 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; } return; } 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=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>a[i][j],dis[i][j]=INT_MAX; if ((2*k+1)*(2*k+1)<=INT_MAX) bfs1(); else ; cout<<dis[ex][ey]<<endl; return 0; }
#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...