Submission

PPPPPPPP

Score: 100

User: Monasm

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.002 second

Submitted On: 2024-12-13 18:23:05

#include<bits/stdc++.h>
using namespace std;

char tb[105][105];
int dist[105][105];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int main()
{
	int N,M;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
		scanf("%s",tb[i]+1);
	
	int x,y;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{
			if(tb[i][j]=='S')
			{
				x=i,y=j;
			}
			
			dist[i][j]=100000;
		}
	int ans=100000;
	
	priority_queue<pair<int,pair<int,int>>> pq;
	/// dist (x,y)
	
	pq.push({0,{x,y}});
	dist[x][y]=0;

	while(!pq.empty())
	{
		x=pq.top().second.first;
		y=pq.top().second.second;
		int k=-pq.top().first;
		pq.pop();
		
		for(int i=0;i<4;i++)
		{
			int nx=x+dx[i];
			int ny=y+dy[i];
			int d =k+(tb[nx][ny]=='#');
			if(d<dist[nx][ny])
			{
				pq.push({-d,{nx,ny}});
				dist[nx][ny]=d;
			}
		}
	}
/*
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
			printf("%d ",dist[i][j]);
		printf("\n");
	}
//*/
	for(int j=1;j<=M;j++)
	{
		ans=min(ans,dist[1][j]);
		ans=min(ans,dist[N][j]);
	}
	for(int i=1;i<=N;i++)
	{
		ans=min(ans,dist[i][1]);
		ans=min(ans,dist[i][M]);		
	}
	printf("%d\n",ans);
}