CSES - Monsters

Dynonychus

Nov 14th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 4.25 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mn = 1005;
int n;
int m;
int i;
int j;
int x;
int y;
int z;
int p;
int q;
vector<string> vec(mn); // Stores Maze
vector<vector<bool>> visM(mn); // Visited by M
vector<vector<bool>> visA(mn); // Visited by A
vector<vector<bool>> block(mn); // Stores wall locations
vector<string> dir(mn); // Stores final path
queue<pair<int, int>> qA;
queue<pair<int, int>> qM;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int a=0;
int b=0;
char c;
string s;
cin>>n>>m;
vec.resize(n);
visA.resize(n);
visM.resize(n);
block.resize(n);
dir.resize(n);
for(i=0;i<n;i++) {
cin>>s;
vec.at(i) = s;
visA.at(i).resize(m);
visM.at(i).resize(m);
block.at(i).resize(m);
dir.at(i).resize(m);
}
for(i=0;i<n;i++) {
for(j=0;j<m;j++) {
if(vec.at(i).at(j) == '#')
block.at(i).at(j) = true;
if(vec.at(i).at(j) == 'M') {
visM.at(i).at(j) = true;
qM.push({i, j});
}
if(vec.at(i).at(j) == 'A') {
visA.at(i).at(j) = true;
qA.push({i, j});
p = i;
q = j;
}
}
}
while(!qA.empty()) {
z = qM.size();
if(z == 0)
goto lol;
while(z--) {
x = qM.front().first;
y = qM.front().second;
qM.pop();
visM.at(x).at(y) = true;
a = (x+1);
b = y;
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visM.at(a).at(b))
qM.push({a, b});
a = (x-1);
b = y;
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visM.at(a).at(b))
qM.push({a, b});
a = x;
b = (y+1);
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visM.at(a).at(b))
qM.push({a, b});
a = x;
b = (y-1);
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visM.at(a).at(b))
qM.push({a, b});
}
i=i;
lol:
z = qA.size();
while(z--) {
x = qA.front().first;
y = qA.front().second;
qA.pop();
if(visM.at(x).at(y))
continue;
visA.at(x).at(y) = true;
if(x == 0 || y == 0 || x == (n-1) || y == (m-1))
goto lol;
a = (x+1);
b = y;
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visA.at(a).at(b) && !visM.at(a).at(b)) {
qA.push({a, b});
dir.at(a).at(b) = 'D';
}
a = (x-1);
b = y;
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visA.at(a).at(b) && !visM.at(a).at(b)) {
qA.push({a, b});
dir.at(a).at(b) = 'U';
}
a = x;
b = (y+1);
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visA.at(a).at(b) && !visM.at(a).at(b)) {
qA.push({a, b});
dir.at(a).at(b) = 'R';
}
a = x;
b = (y-1);
if(a < n && a >= 0 && b < m && b >= 0 && !block.at(a).at(b) && !visA.at(a).at(b) && !visM.at(a).at(b)) {
qA.push({a, b});
dir.at(a).at(b) = 'L';
}
}
}
a=0;
for(j=0;j<m;j++) {
if(visA.at(0).at(j) || visA.at(n-1).at(j)) {
a = -1;
if(visA.at(0).at(j))
x = 0;
else
x = (n-1);
y = j;
break;
}
}
for(i=0;i<n;i++) {
if(visA.at(i).at(0) || visA.at(i).at(m-1)) {
a = -1;
if(visA.at(i).at(0))
y = 0;
else
y = (m-1);
x = i;
break;
}
}
if(a == -1) {
cout<<"YES"<<endl;
a=0;
s.clear();
while(!(x == p && y == q)) {
s += dir.at(x).at(y);
if(dir.at(x).at(y) == 'U')
x++;
else if(dir.at(x).at(y) == 'D')
x--;
else if(dir.at(x).at(y) == 'R')
y--;
else
y++;
a++;
}
reverse(s.begin(), s.end());
cout<<a<<endl;
cout<<s<<endl;
}
else
cout<<"NO"<<endl;
return 0;
}

Add Comment

Please, Sign In to add comment