关于早上的D题
  • 板块学术版
  • 楼主AAA404
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/2/4 15:44
  • 上次更新2023/10/24 01:44:11
查看原帖
关于早上的D题
723198
AAA404楼主2023/2/4 15:44

公告说大样例和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秒

2023/2/4 15:44
加载中...