公告说大样例和std有误,我大样例测的结果是71,有没有和我一样的,我两个小样例都手模无误且过了。
下面是我的代码
#include<bits/stdc++.h>
using namespace std;
int n,m,dx[2]={1,0},dy[2]={0,1},ans[9001][1001],xx,yy;
bool vis[9001][1001];
char a[9001][1001];
inline int read()
{
char ch=getchar();int s=0,w=1;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9'){s=s*10+ch-48;ch=getchar();}
return s*w;
}
struct node{
int x,y,step;
};
queue<node>q;
void bfs(int x,int y)
{
q.push({x,y,0});
vis[x][y]=1;
ans[x][y]=0;
while(!q.empty())
{
for(int i=0;i<=1;i++)
{
int nx,ny,nstep;
if(a[q.front().x][q.front().y]>='1' && a[q.front().x][q.front().y]<='0'+n)
{
nx=m*(a[q.front().x][q.front().y]-'0'-1)+1,ny=1,nstep=q.front().step;
if(a[nx][ny]=='@')
{
cout<<nstep;
ans[nx][ny]=nstep;
return;
}
if(nx>=1 && nx<=n*m && ny>=1 && ny<=m && a[nx][ny]!='*' && nstep<ans[nx][ny])
{
q.push({nx,ny,nstep});
vis[nx][ny]=1;
ans[nx][ny]=nstep;
break;
}
}
else
{
nx=q.front().x+dx[i],ny=q.front().y+dy[i],nstep=ans[q.front().x][q.front().y]+1;
if(a[nx][ny]=='@')
{
cout<<nstep;
ans[nx][ny]=nstep;
return;
}
if(nx>=1 && nx<=n*m && ny>=1 && ny<=m && !vis[nx][ny] && a[nx][ny]!='*' && nstep<ans[nx][ny])
{
q.push({nx,ny,nstep});
vis[nx][ny]=1;
ans[nx][ny]=nstep;
}
}
}
q.pop();
}
}
int main()
{
//freopen("1.in","r",stdin);
// freopen(".out","w",stdout);
memset(ans,0x3f,sizeof ans);
n=read(),m=read();
for(int i=1;i<=n*m;i++)
{
scanf("%s",a[i]+1);
for(int j=1;j<=m;j++)if(a[i][j]=='@')xx=i,yy=j;
}
if(a[1][1]=='*')
{
cout<<"-1";
return 0;
}
bfs(1,1);
if(ans[xx][yy]==0x3f3f3f3f)
{
cout<<"-1";
return 0;
}
return 0;
}
ps:呜呜呜早上没起来错过了比赛,等我想起来是比赛剩10秒