Submission

Score: 0

User: navysrimuang

Problemset: anna

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-18 19:44:10

#include<bits/stdc++.h>
using namespace std;
using T = tuple<int, string, int, int>;
const int INF = 1e8;
int best = INF;
//dijkstra with sliding and string
char tushar[] = {'d','l','r','u'};
int dr[] = {1,0,0,-1};
int dc[] = {0,-1,1,0};
int n,m;
int sr,sc,er,ec;
priority_queue<T, vector<T>, greater<T>> pq;
vector<string> ans;

void solve(){
	cin >> n >> m;
	vector<vector<int>> g(n+2,vector<int>(m+2,1));
	vector<vector<int>> dist(n+2,vector<int>(m+2,INF));
	for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) cin >> g[i][j];
	cin >> sr >> sc >> er >> ec;
	sr++; sc++; er++; ec++;
	dist[sr][sc] = 0;
	pq.push({0,"",sr,sc});	

	while(pq.size()){
		auto [t,s,r,c] = pq.top();
		pq.pop();

		if(t > dist[r][c]) continue;

		for(int i = 0;i<4;i++){
			int nr = r; int nc = c;
			int cnt = 0;
			while(true){

				int tr = nr+dr[i]; int tc = nc+dc[i];
				if(tr < 1 || tr > n || tc < 1 || tc > m) break;
				if(g[tr][tc]) break;
				
				cnt++;
				nr = tr;
				nc = tc;	

				if(nr == er && nc == ec){
					string ns = s+tushar[i];
					if(t+cnt < best){
						best = t+cnt;
						ans.clear();
						ans.push_back(ns);
					}else if(t+cnt == best){
						ans.push_back(ns);
					}					
					break;
				}
			}
			if(cnt == 0) continue;
			string ns = s+tushar[i];
			if(t + cnt <= dist[nr][nc]){
				dist[nr][nc] = t + cnt;
				pq.push({dist[nr][nc],ns,nr,nc});
			}
		}
	}

	if(ans.empty()){
		cout << "NO\n";
		return;
	}
	sort(ans.begin(),ans.end());
	cout << ans[0] << "\n";
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	solve();
	return 0;
}