提出 #71685879

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
int cnt=0;
struct z{
	int x,y;
}b[1000005];
bool vis[10005][1005];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int h,w;
int step[1005][1005];
void bfs(int x,int y){
	memset(step,-1,sizeof step);
	queue<pair<int,int> >q;
	q.push({x,y});
	vis[x][y]=true;
	while(!q.empty())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=t.first+dx[i];
			int ny=t.second+dy[i];
			if(nx>=1&&nx<=h&&ny>=1&&ny<=w&&!vis[nx][ny])
			{
				vis[nx][ny]=true;
				step[nx][ny]=step[t.first][t.second]+1;
				q.push({nx,ny});
			}
		}
		if(a[t.first][t.second]=='a')
		{
			for(int i=1;i<=cnt;i++)
			{
				int nx=b[i].x;
				int ny=b[i].y;
				if(nx>=1&&nx<=h&&ny>=1&&ny<=w&&!vis[nx][ny])
				{	
					vis[nx][ny]=true;
					step[nx][ny]=step[t.first][t.second]+1;
					q.push({nx,ny});
				}
			}
		}
	}
}
int main()
{
	cin>>h>>w;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			cin>>a[i][j];
			if(a[i][j]>='a'&&a[i][j]<='z')
			{
				b[++cnt].x=i;
				b[++cnt].y=j;	
				a[i][j]='a';
			}
		}
	}
	bfs(1,1);
	cout<<step[h][w];
	return 0;
 } 

提出情報

ジャッジ結果