QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799265 | #5514. Maze | sichengzhou | 0 | 1ms | 5916kb | C++17 | 1.6kb | 2024-12-05 09:46:55 | 2024-12-05 09:46:56 |
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 s;
int R,C,n,Sr,Sc,Gr,Gc;
int q[N];
#define id(x,y) ((x-1)*n+(y-1))
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int d[N];
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>>s;s=" "+s;
a.push_back(s);
}
int 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;
while(hh<=tt)
{
for(int i=hh;i<=tt;i++)
{
auto [x,y]=get(q[i]);
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(a[tx][ty]=='.'&&d[id(tx,ty)]==-1)
{
d[id(tx,ty)]=d[q[i]];
q[++tt]=id(tx,ty);
}
}
}
// cout<<hh<<'*'<<tt<<'\n';
int cur=tt;
while(hh<=cur)
{
auto [x,y]=get(q[hh]);
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;
q[++tt]=id(tx,ty);
}
}
// cout<<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: 1ms
memory: 5916kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
8
result:
wrong answer 1st lines differ - expected: '26', found: '8'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 0
Wrong Answer
time: 1ms
memory: 5620kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'
Subtask #3:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 1ms
memory: 5688kb
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%