QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#124270 | #411. Dangerous Skating | tcwxxxx | 0 | 653ms | 188564kb | C++14 | 2.3kb | 2023-07-14 15:37:07 | 2023-07-14 15:37:08 |
Judging History
answer
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
long long y,z;
};
char a[1010][1010];
vector<node>b[1000010];
long long dis[1000010];
long long fx[5]={0,0,0,1,-1};
long long fy[5]={0,1,-1,0,0};
bool vis[1000010];
void dij(long long s)
{
long long i;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<pair<long long,long long>>q;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
long long t=q.top().second;
q.pop();
if(vis[t]==1)
{
continue;
}
vis[t]=1;
for(i=0;i<b[t].size();i++)
{
long long yy=b[t][i].y,zz=b[t][i].z;
if(dis[yy]>dis[t]+zz)
{
dis[yy]=dis[t]+zz;
q.push(make_pair(-dis[yy],yy));
}
}
}
return ;
}
int main()
{
long long n,m,x,y,x1,y1,i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
cin>>x>>y>>x1>>y1;
for(i=1;i<=n;i++)
{
long long la=0;
for(j=1;j<=m;j++)
{
if(a[i][j]=='#')
{
la=j;
}
else
{
if(la!=j-1)
{
node e;
e.y=i*m+la+1-m;
e.z=1;
b[i*m+j-m].push_back(e);
}
}
}
la=0;
for(j=m;j>=1;j--)
{
if(a[i][j]=='#')
{
la=j;
}
else
{
if(la!=j+1)
{
node e;
e.y=i*m+la-1-m;
e.z=1;
b[i*m+j-m].push_back(e);
}
}
}
}
for(i=1;i<=m;i++)
{
long long la=0;
for(j=1;j<=n;j++)
{
if(a[j][i]=='#')
{
la=j;
}
else
{
if(la!=j-1)
{
node e;
e.y=la*m+i;
e.z=1;
b[j*m+i-m].push_back(e);
}
}
}
la=0;
for(j=n;j>=1;j--)
{
if(a[j][i]=='#')
{
la=j;
}
else
{
if(la!=j+1)
{
node e;
e.y=la*m+i-2*m;
e.z=1;
b[j*m+i-m].push_back(e);
}
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]=='.')
{
long long xx,yy;
for(k=1;k<=4;k++)
{
xx=i+fx[k];
yy=j+fy[k];
if(xx<1||xx>n||yy<1||yy>m)
continue;
if(a[xx][yy]=='.')
{
node e;
e.y=xx*m+yy-m;
e.z=2;
b[i*m+j-m].push_back(e);
}
}
}
}
}
dij(x*m+y-m);
if(dis[x1]*m+y1-m>1e9)
{
cout<<-1;
}
else
{
cout<<dis[x1*m+y1-m];
}
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: 0ms
memory: 35704kb
input:
10 10 ########## #....#.### #.......## #........# #.......## ##.......# #.......## #.....#.## #.....#..# ########## 4 7 8 5
output:
-1
result:
wrong answer 1st lines differ - expected: '6', found: '-1'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 17ms
memory: 42488kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
-1
result:
wrong answer 1st lines differ - expected: '69', found: '-1'
Subtask #3:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 653ms
memory: 188564kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
-1
result:
wrong answer 1st lines differ - expected: '126', found: '-1'