QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799330 | #5514. Maze | sichengzhou | 0 | 3ms | 16156kb | C++17 | 4.0kb | 2024-12-05 11:04:59 | 2024-12-05 11:04:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=6e6+6;
#define mkp make_pair
vector<string>a;
string str;
int R,C,n,Sr,Sc,Gr,Gc;
int q[N];
#define id(x,y) ((x-1)*C+(y-1))
#define mid (l+r)/2
#define mi (i+j)/2
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int d[N];
int c[N<<2],s[4][N<<2],rt,tot,hh,tt;
int x,y,u,v,V;
void upd(int p)
{
c[p]=0;
for(int i=0;i<4;i++)
{
c[p]+=c[s[i][p]];
}
}
void init(int& p,int l,int r,int i,int j)
{
if(l>r||i>j)
{
return ;
}
p=++tot;
// printf("init(%d,%d,%d,%d,%d)\n",p,l,r,i,j);
if(l==r&&i==j)
{
c[p]=1;
return ;
}
init(s[0][p],l,mid,i,mi);
init(s[1][p],l,mid,mi+1,j);
init(s[2][p],mid+1,r,i,mi);
init(s[3][p],mid+1,r,mi+1,j);
upd(p);
}
void erase(int p,int l,int r,int i,int j)
{
if(r<x||y<l||j<u||v<i||l>r||i>j||c[p]==0)
{
return;
}
if(l==r&&i==j)
{
c[p]=0;
return ;
}
erase(s[0][p],l,mid,i,mi);
erase(s[1][p],l,mid,mi+1,j);
erase(s[2][p],mid+1,r,i,mi);
erase(s[3][p],mid+1,r,mi+1,j);
upd(p);
}
void query(int p,int l,int r,int i,int j)
{
if(r<x||y<l||j<u||v<i||l>r||i>j||c[p]==0)
{
return;
}
// printf("query(%d,%d,%d,%d,%d)\n",p,l,r,i,j);
if(l==r&&i==j)
{
if((l==x||l==y)&&(i==u||i==v))
{
return ;
}
// cout<<V<<' '<<l<<' '<<i<<'\n';
d[id(l,i)]=d[V]+1;
q[++tt]=id(l,i);
c[p]=0;
return ;
}
query(s[0][p],l,mid,i,mi);
query(s[1][p],l,mid,mi+1,j);
query(s[2][p],mid+1,r,i,mi);
query(s[3][p],mid+1,r,mi+1,j);
upd(p);
}
int main()
{
cin>>R>>C>>n>>Sr>>Sc>>Gr>>Gc;
auto get=[&](int id){
return mkp(id/C+1,id%C+1);
};
a.push_back(" ");
for(int i=1;i<=R;i++)
{
cin>>str;str=" "+str;
a.push_back(str);
}
init(rt,1,R,1,C);
hh=1,tt=0;
q[++tt]=id(Sr,Sc);
for(int i=0;i<R*C;i++)
{
d[i]=-1;
}
d[id(Sr,Sc)]=0;
x=y=Sr;u=v=Sc;
erase(1,1,R,1,C);
while(hh<=tt)
{
for(int i=hh;i<=tt;i++)
{
auto [l,r]=get(q[i]);
for(int k=0;k<4;k++)
{
int tx=l+dx[k],ty=r+dy[k];
if(tx<1||tx>R||ty<1||ty>C)
{
continue;
}
if(a[tx][ty]=='.'&&d[id(tx,ty)]==-1)
{
//pr cout<<tt<<' '<<tx<<' '<<ty<<a[tx][ty]<<'\n';
d[id(tx,ty)]=d[q[i]];
x=y=tx;u=v=ty;
erase(1,1,R,1,C);
q[++tt]=id(tx,ty);
}
}
}
// cout<<hh<<'*'<<tt<<'\n';
int cur=tt;
while(hh<=cur)
{
auto [l,r]=get(q[hh]);
x=l-n;y=l+n;u=r-n;v=r+n;V=d[q[hh]];
query(1,1,R,1,C);
hh++;
continue;
if(R*C<=1000)
{
for(int tx=1;tx<=R;tx++)
{
for(int ty=1;ty<=C;ty++)
{
if(abs(tx-x)+abs(ty-y)<=2*n-1&&abs(tx-x)<=n&&abs(ty-y)<=n)
{
if(d[id(tx,ty)]==-1)
{
d[id(tx,ty)]=d[q[hh]]+1;
// cout<<tt<<' '<<x<<' '<<y<<' '<<tx<<' '<<ty<<'\n';
q[++tt]=id(tx,ty);
}
}
}
}
hh++;
continue;
}
for(int k=0;k<4;k++)
{
int tx=x+dx[k],ty=y+dy[k];
if(tx<1||tx>R||ty<1||ty>C)
{
continue;
}
if(d[id(tx,ty)]==-1)
{
d[id(tx,ty)]=d[q[hh]]+1;
// cout<<tt<<' '<<x<<' '<<y<<' '<<tx<<' '<<ty<<'\n';
q[++tt]=id(tx,ty);
}
}
// cout<<hh<<' '<<x<<' '<<y<<' '<<d[id(x,y)]<<endl;
hh++;
}
}
cout<<d[id(Gr,Gc)]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 16156kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
0
result:
wrong answer 1st lines differ - expected: '26', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 19
Accepted
time: 0ms
memory: 11800kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
0
result:
ok single line: '0'
Test #53:
score: 19
Accepted
time: 2ms
memory: 11804kb
input:
4 24 4 3 4 3 3 ..#...##.#...###...###.# .##.#..##.##.##..#.####. #.......#.#.#...#.#####. ######....######.#...#.#
output:
0
result:
ok single line: '0'
Test #54:
score: 0
Wrong Answer
time: 0ms
memory: 11864kb
input:
2 136 2 1 133 2 45 #############################################.##################.#.#######.##############.#################.##############.##.######.### ####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################
output:
0
result:
wrong answer 1st lines differ - expected: '41', found: '0'
Subtask #3:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 3ms
memory: 15820kb
input:
35 60 20 3 60 2 44 .#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####. #.#......#.####..####...#...#......#........####....##.#.### .#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##. .#.#...##..#.##.......#......##......####...##.##..##.#....# #...#.......#..#..#...#.#####.##.###....
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%