Submission

Score: 100

User: kavin8888

Problemset: Sirabyrinth 1

Language: cpp

Time: 0.003 second

Submitted On: 2025-12-19 11:49:21

#include<bits/stdc++.h>
using namespace std;
int n,m;
const string INF="";
vector<vector<char>> a;
vector<vector<int>> cost;
vector<vector<string>> dist;
queue<pair<int,int>> q;
// x y c
tuple<int,int,char> DI[4]={{-1,0,char('U')},{1,0,char('D')},{0,-1,char('L')},{0,1,char('R')}};
bool valid(int x,int y) {
	return 0<=x && x<n && 0<=y && y<m;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin>>n>>m;
	a.assign(n,vector<char>(m));
	cost.assign(n,vector<int>(m,INT_MAX));
	dist.assign(n,vector<string>(m,INF));
	for(int i=0;i<n;++i) {
		for(int j=0;j<m;++j) {
			cin>>a[i][j];
			if(a[i][j]=='S') {
				cost[i][j]=0;
				q.push({i,j});
			}
		}
	}
	while(!q.empty()) {
		auto [x,y] =q.front(); q.pop();
		if(x==0 || x==n-1 || y==0 || y==m-1) {
			cout<<cost[x][y]<<'\n'<<dist[x][y];
			return 0;
		}
		for(auto [di,dj,dc] : DI) {
			int dx=x+di,dy=y+dj;
			if(!valid(dx,dy)) continue;
			if(a[dx][dy]=='#') continue;
			if(cost[x][y]+1<cost[dx][dy]) {
				cost[dx][dy]=cost[x][y]+1;
				dist[dx][dy]=dist[x][y]+dc;
				q.push({dx,dy});
			}
		}
	}
}