| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785649 |
2023-07-17T11:17:36 Z |
KLPP |
Maze (JOI23_ho_t3) |
C++14 |
|
1 ms |
212 KB |
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int r,c,n;
int valid(int x, int y){
if(x>=0 && x<r && y>=0 && y<c)return true;
return false;
}
bitset<350000000> b;
#define MAX 24
deque<tuple<int,int,int> >q;
vector<vector<int> >dist;
int D;
void solve(int x, int y, int N, int cnt){
int hsh=cnt+MAX*(y+n+(c+n)*(x+n));
b[hsh]=1;
if(N==1){
if(valid(x,y) && dist[x][y]==-1){
dist[x][y]=D+1;
q.push_back({x,y,D+1});
}
return;
}
if(N%2==0){
N/=2;
solve(x,y,N,cnt+1);
solve(x+N,y,N,cnt+1);
solve(x,y+N,N,cnt+1);
solve(x+N,y+N,N,cnt+1);
return;
}
N/=2;
solve(x,y,N+1,cnt+1);
solve(x+N,y,N+1,cnt+1);
solve(x,y+N,N+1,cnt+1);
solve(x+N,y+N,N+1,cnt+1);
}
void solve(){
cin>>r>>c>>n;
int sx,sy;
cin>>sx>>sy;
sx--;sy--;
int gx,gy;
cin>>gx>>gy;
gx--;gy--;
vector<string> V(r);
rep(i,0,r)cin>>V[i];
dist.resize(r);
rep(i,0,r)dist[i].resize(c,1000000000);
dist[sx][sy]=0;
q.push_back({sx,sy,0});
while(!q.empty()){
auto [x,y,d]=q.front();
q.pop_front();
D=d;
if(d>dist[x][y])continue;
if(V[x][y]=='.'){
rep(dx,x-1,x+2){
rep(dy,y-1,y+2){
if(abs(dx-x)+abs(dy-y)==1){
if(valid(dx,dy)){
if(dist[dx][dy]>d){
dist[dx][dy]=d;
q.push_front({dx,dy,d});
}
}
}
}
}
}
solve(x-n,y-n+1,2*n-1,0);
solve(x-n+1,y-n,2*n-1,0);
solve(x-n+1,y-n+1,2*n-1,0);
solve(x-n+2,y-n+1,2*n-1,0);
solve(x-n+1,y-n+2,2*n-1,0);
}
cout<<dist[gx][gy]<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
//cin>>tt;
while(tt--){
solve();
}
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:64:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | auto [x,y,d]=q.front();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
