Submission

--P-P-PP

Score: 52

User: Nathlol2

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.004 second

Submitted On: 2025-01-26 14:38:49

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	string a[n];
	int sx, sy;
	for(int i = 0;i<n;i++){
		cin >> a[i];
		for(int j = 0;j<m;j++){
			if(a[i][j] == 'S'){
				sx = i;
				sy = j;
			}
		}
	}
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
	vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
	dist[sx][sy] = 0;
	pq.push({0, sx, sy});
	while(!pq.empty()){
		auto [d, x, y] = pq.top();
		pq.pop();
		for(int i = 0;i<4;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m){
				continue;
			}
			if(a[nx][ny] == '#')
				d++;
			if(d < dist[nx][ny]){
				pq.push({d, nx, ny});
				dist[nx][ny] = d;
			}
		}
	}
	int ans = INT_MAX;
	for(int j = 0;j<m;j++){
		ans = min(ans,dist[0][j]);
		ans = min(ans,dist[n - 1][j]);
	}
	for(int i = 0;i<n;i++){
		ans = min(ans,dist[i][0]);
		ans= min(ans,dist[i][m - 1]);		
	}
	cout << ans << '\n';
}