In this HackerEarth Robotic paths problem solution, You have built a new robot and placed it in a maze. The maze contains N rows and each row contains M cells. Each cell of the maze is either an empty cell or an obstacle. An empty cell is denoted by a (.) dot and an obstacle is denoted by a (#) hash. The robot is operated by your computer with some keyboard commands. Currently, there are 4 character commands:
- L: Moves the robot from the current cell to its left cell
- R: Moves the robot from the current cell to its right cell
- U: Moves the robot from the current cell to its upper cell
- D: Moves the robot from the current cell to its lower cell
The robot can go to some cell only if it is empty and inside the maze. Therefore, you cannot give a command that takes the robot to an obstacle or out of the maze.
The robot is currently at (sx,sy) cell. You want to take it to (fx,fy) cell. Therefore, you are required to build a string of character commands that takes the robot to the destination. There may exist several strings that can perform the same task but you must use the string of the minimum length. If there exist several strings of the minimum length, you must select the lexicographically smallest string of them.
HackerEarth Robotic paths problem solution.
#include<bits/stdc++.h>
using namespace std;
#define fRead(x) freopen(x,"r",stdin)
#define fWrite(x) freopen (x,"w",stdout)
#define LL long long
#define ULL unsigned long long
#define ff first
#define ss second
#define pb push_back
#define INF 2e16
#define PI acos(-1.0)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<LL,LL>
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(a,min(b,min(c,d)))
#define max4(a,b,c,d) max(a,max(b,max(c,d)))
#define SQR(a) ((a)*(a))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,b) for(int i=0;i<b;i++)
#define MEM(a,x) memset(a,x,sizeof(a))
#define ABS(x) ((x)<0?-(x):(x))
#define SORT(v) sort(v.begin(),v.end())
#define REV(v) reverse(v.begin(),v.end())
#define FastRead ios_base::sync_with_stdio(0);cin.tie(nullptr);
char str[105][105];
int n,m,q;
int dis[105][105];
bool vis[105][105];
int dx[ ] = {1,0,0,-1};
int dy[ ] = {0,-1,1,0};
string com = "DLRU";
int check(int x,int y)
{
if(x >= 0 and y >= 0 and x < n and y < m and str[x][y] == '.')return 1;
else return 0;
}
void bfs(int sx,int sy,int fx,int fy)
{
MEM(vis,0);
queue<pii>Q;
Q.push(mk(fx,fy));
vis[fx][fy] = 1;
while(!Q.empty()){
pii P = Q.front();
Q.pop();
for(int i = 0;i < 4;i++){
int X = P.first + dx[i];
int Y = P.second + dy[i];
if(check(X,Y) and vis[X][Y] == 0){
vis[X][Y] = 1;
dis[X][Y] = dis[P.first][P.second] + 1;
Q.push(mk(X,Y));
}
}
}
if(vis[sx][sy] == 0){
printf("Impossible\n");
return;
}
string ans;
while(1){
if(sx == fx and sy == fy)break;
for(int i = 0;i < 4;i++){
int X = sx + dx[i];
int Y = sy + dy[i];
if(check(X,Y) == 1 and dis[X][Y] + 1 == dis[sx][sy]){
sx = X , sy = Y;
ans = ans + com[i];
break;
}
}
}
cout << ans << "\n";
}
int main()
{
scanf("%d %d",&n,&m);
REP(i,n)scanf("%s",str[i]);
scanf("%d",&q);
while(q--){
int sx,sy,fx,fy;
scanf("%d %d %d %d",&sx,&sy,&fx,&fy);
sx--;sy--;fx--;fy--;
bfs(sx,sy,fx,fy);
}
}Second solution
#include<bits/stdc++.h>
#define ll unsigned long long
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 2e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
char s[55][55];
string str="DLRU";
int rr[4]={1,0,0,-1};
int cc[4]={0,-1,1,0};
bool vis[55][55];
int dist[55][55];
int main() {
int n,m; cin>>n>>m;
assert(n>=3 && n<=50);
assert(m>=3 && m<=50);
for(int i=0;i<n;i++) {
cin>>s[i];
}
int q; cin>>q;
assert(q>=1 && q<=300);
while(q--) {
int sx,sy,fx,fy;
cin>>sx>>sy>>fx>>fy;
assert(sx>=1 && sx<=n);
assert(sy>=1 && sy<=m);
assert(fx>=1 && fx<=n);
assert(fy>=1 && fy<=m);
sx--,sy--,fx--,fy--;
mem(vis,0); mem(dist,0);
queue< pii >qe;
vis[fx][fy]=true;
qe.push({fx,fy});
while(!qe.empty()) {
pii p=qe.front();
qe.pop();
int r=p.F,c=p.S;
for(int i=0;i<4;i++) {
int tr=r+rr[i];
int tc=c+cc[i];
if(tr>=0 && tr<n && tc>=0 && tc<m && !vis[tr][tc] && s[tr][tc]=='.') {
vis[tr][tc]=true;
dist[tr][tc]=dist[r][c]+1;
qe.push({tr,tc});
}
}
}
if(!vis[sx][sy]) {
cout<<"Impossible\n";
continue;
}
string ans="";
while(1) {
if(sx==fx && sy==fy) break;
for(int i=0;i<4;i++) {
int tr=sx+rr[i];
int tc=sy+cc[i];
if(tr>=0 && tr<n && tc>=0 && tc<m && s[tr][tc]=='.' && dist[tr][tc]+1==dist[sx][sy]) {
sx=tr,sy=tc; ans=ans+str[i];
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}
0 Comments