QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #414849 | #6739. Teleport | Arnold_6 | AC ✓ | 387ms | 35444kb | C++17 | 2.9kb | 2024-05-19 22:06:36 | 2024-05-19 22:06:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,k;
char mp[5005][5005];
int arr[15005];
bool v[5005][5005];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>mp[i]+1;
}
queue<pair<pair<int,int>,int> >q;
q.push({{1,1},0});
arr[n]=1;
v[1][1]=1;
while(q.size())
{
int x=q.front().first.first;
int y=q.front().first.second;
int step=q.front().second;
q.pop();
// cout<<"step="<<step<<" x="<<x<<" y="<<y<<endl;
if(x==n && y==n)
{
cout<<step;
return 0;
}
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>n || v[nx][ny] || mp[nx][ny]=='*')continue;
q.push({{nx,ny},step+1});
v[nx][ny]=1;
arr[n+nx-ny]=max(arr[n+nx-ny],ny);
}
// int tx,ty,t;
// tx=x-y+arr[n+x-y];
// ty=arr[n+x-y];
// t=2*(tx-x);
// // cout<<"t="<<t<<" tx="<<tx<<" ty="<<ty<<endl;
// for(int i=2+t;i<=k;i+=2)
// {
// tx+=1;
// ty+=1;
// // cout<<"step="<<step<<" tx="<<tx<<" ty="<<ty<<endl;
// if(tx>n || ty>n)break;
// if(v[tx][ty] || mp[tx][ty]=='*')continue;
// v[tx][ty]=1;
// arr[n+tx-ty]=ty;
// q.push({{tx,ty},step+1});
// }
// tx=y+1-x+arr[n+y+1-x];
// ty=arr[n+y+1-x];
// t=1+2*(ty-x);
// if(tx>0&&ty>0&&!v[tx][ty]&&mp[tx][ty]!='*')q.push({{tx,ty},step+1}),v[tx][ty]=1;
// for(int i=2+t;i<=k;i+=2)
// {
// tx+=1;
// ty+=1;
// // cout<<"step="<<step<<" tx="<<tx<<" ty="<<ty<<endl;
// if(tx>n || ty>n)break;
// if(v[tx][ty] || mp[tx][ty]=='*')continue;
// v[tx][ty]=1;
// arr[n+tx-ty]=ty;
// q.push({{tx,ty},step+1});
// }
int nx=x,ny=y;
for(int i=2;i<=k;i+=2)
{
nx+=1;
ny+=1;
// cout<<"? "<<nx<<" "<<ny<<" "<<mp[nx][ny]<<" "<<v[nx][ny]<<endl;
if(nx>n || ny>n)break;
if(mp[nx][ny]=='*'||v[nx][ny])continue;
v[nx][ny]=1;
q.push({{nx,ny},step+1});
// cout<<"nw "<<nx<<" "<<ny<<endl;
}
nx=y+1,ny=x;
if(!v[nx][ny] && mp[nx][ny]!='*')
{
v[nx][ny]=1;
q.push({{nx,ny},step+1});
}
for(int i=3;i<=k;i+=2)
{
nx+=1;
ny+=1;
if(nx>n || ny>n)break;
if(mp[nx][ny]=='*'||v[nx][ny])continue;
v[nx][ny]=1;
q.push({{nx,ny},step+1});
}
}
cout<<-1;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5568kb
input:
3 2 .*. .*. ...
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5760kb
input:
3 3 .*. .*. ...
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 35ms
memory: 16304kb
input:
961 4 ...*.*..*.....*.*..*..*..*.*.*.*.....*.....*....*..*...*....*.........*....*....*...*......*..*..*...*..*...*.....*...*...*.*.*.........**..**.......*.......*...*...*.*.*........*....*..*..*...*.....*.*......**.**..**...*..*.**.....*....*.*.*..*..*..*.*..*.*..*......*..*..*.*......*...*.*...*....
output:
540
result:
ok 1 number(s): "540"
Test #4:
score: 0
Accepted
time: 13ms
memory: 13524kb
input:
975 434 .*......*...*....*......*..*...*...**....*....*.......*...*.....*..*..*.*.*..*.*..*..*.*....*.*.*..*...*.*.....*......*.*...*......*..*..*......**..**.......*...*.*..*..*.*.**....*.*.*.....*....**.*..*..**.*..*.....*.*......*..*...*..*...*....**...*....*..*.*.*...........*..*.**.*.*..*.*..**...
output:
5
result:
ok 1 number(s): "5"
Test #5:
score: 0
Accepted
time: 23ms
memory: 13584kb
input:
966 19 ..*.*.*........*.*..*.**..*....*..*..*....*.**..*.*.*..*.*.*..**....*.*.*....*.....*...........*.*..*.....*..*...*....*.*...*.*...*....*...*...*.*.*....*.*....**.*.......*....*.*.*...*..*..*..*.*...*...*...*..*..*..........*.*....*.*......*...*..**....*.*....**.....*..*..*..*.*....*...*..*.*....
output:
104
result:
ok 1 number(s): "104"
Test #6:
score: 0
Accepted
time: 17ms
memory: 13628kb
input:
973 199 ..**.*...*.*...*.*.*.*.**..*.*.*..*......*.....*.*.*..*...**.....*.*..*.*..*...*....*..*...*....*.*...*.*......*..*.*.*.*......**......*.*.*.*.*.*...*...*...*....*......*.*.*.*..*..*..*...*..*.*....*....*.*...*..*..*.*..**.**..*.**....*.*...*..**..**...*......*.....*.....*..*.*.......*.*.*.....
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 12ms
memory: 15668kb
input:
984 95 .....*.*...*....*..*....*.*....**.**......*....*.*.*.......*.....*.*..*....*..*....*.*.....*..*.......*.*......*.*....*.....*......*...*....*....*......*....*.*...*........*......*.*....*.*...*....*..**....*.*.*.**....*..*.*..*..*.*......*..*......*.*......*...*......*.......*...*....*...**.....
output:
21
result:
ok 1 number(s): "21"
Test #8:
score: 0
Accepted
time: 387ms
memory: 35444kb
input:
2996 2 ..*..*.....*..*.....*....**..*...........*..*........*..*..*.*..*..*.*.*.**.*.....**.*.......*.......*..*....*.....*..*.*.*....**.....*..**.....*.....*.......*.*.*.*....*...*..*.**......**..*.*...**..*..*......*..*.*...*......*.*.*.*...**.**..*.*........*.*..*...**......*.*..*.*..*....*.*.*.*...
output:
3354
result:
ok 1 number(s): "3354"
Test #9:
score: 0
Accepted
time: 101ms
memory: 31812kb
input:
2905 1023 .........*..*.**.....*...*.*....*.*.**.*..*...*..*....*...*.**.*.*.**..*......*...*.**..*...*..*.........*.........*.*.....**.*.*........*.....*.*....*..*.*.....*..*..*..*.*..*....**...*.*..*....*......*.........*.*.*.*......**.**.**..*.*.*..*..**..*..*...*...*.*.......*..*..*....*.*.........
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 129ms
memory: 32092kb
input:
2978 104 .*.........*...**.....*...*........*..*...*.*.*.....*........*.*...*.....*...*....*...*..*...*..*..*....*...*..*.*....*....*...*.......*.*.....*.*.......*.*..*...*.*.......*.*.*..........*.*..*.*..**.*....*.*.*..*...*.*.*.....*....*...*.*.*.*.........*.*.....**.*.*..*.*....*........*...*.**...
output:
58
result:
ok 1 number(s): "58"