Labyrinth
unknown
c_cpp
3 years ago
2.9 kB
8
Indexable
#include<bits/stdc++.h> using namespace std; #define ll long long #define rep(i,a,b) for(int i = a; i<b; i++) #define rew(x) for(int i = 0; i<x; i++) #define deb(x) cout<<"\n"<<#x <<": "<<x<<"\n"; #define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);} #define endl "\n" //DEBUGGER #ifndef ONLINE_JUDGE #include<pprint.hpp> pprint::PrettyPrinter _printer(std::cerr); #define de(...) _printer.compact(true).print('[', #__VA_ARGS__,"] =", __VA_ARGS__) #define de2(...) _printer.compact(false).print('[', #__VA_ARGS__,"] =", __VA_ARGS__) #endif #ifdef ONLINE_JUDGE // https://github.com/p-ranav/pprint #define de(...) #define de2(...) #endif // DEBUGGER CODE ENDS int n,m; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; char dc[] = {'U', 'R', 'D', 'L'}; // Input grid vector<string> v; // To store from which direction we came from vector<vector<char>> path; vector<vector<bool>> vis(1001,vector<bool> (1001,false)); vector<vector<pair<int,int>>> parent; // To check if it's in the bound, is not visited and is not a wall bool isValid(int x, int y){ return ((x>=0 && x<n && y>=0 && y < m) && (!vis[x][y]) && v[x][y] != '#'); } void bfs(int i, int j){ queue<pair<int,int>> q; q.push({i,j}); path[i][j] = ';'; // MArking the initial cell while(!q.empty()){ pair<int,int> curr = q.front(); q.pop(); vis[curr.first][curr.second] = 1; rep(t,0,4){ int x = curr.first + dx[t]; int y = curr.second + dy[t]; if(isValid(x,y)){ parent[x][y] = curr; path[x][y] = dc[t]; if(v[x][y] == 'B'){ return; } q.push({x,y}); } } } } void solve(){ cin>>n>>m; rew(n){ string a; cin>>a; v.push_back(a); } // Intializing path and parent according to n,m path = vector<vector<char>> (n,vector<char> (m, '.')); parent = vector<vector<pair<int,int>>> (n,vector<pair<int,int>> (m,{-1,-1})); pair<int,int> start,end; rep(i,0,n){ rep(j,0,m){ if(v[i][j] == 'A'){ start = {i,j}; }else if(v[i][j] == 'B'){ end = {i,j}; } } } bfs(start.first,start.second); // To check if we ever reached B or not if(path[end.first][end.second] == '.'){ cout<<"NO"; return; } pair<int,int> curr = end; string ans = ""; while(curr != start){ ans += path[curr.first][curr.second]; curr = parent[curr.first][curr.second]; } reverse(ans.begin(),ans.end()); cout<<"YES\n"; cout<<ans.size()<<endl; cout<<ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
Editor is loading...