Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- using namespace std;
- int prev_step[1005][1005];
- int main()
- {
- ios_base::sync_with_stdio(false);
- cout.tie(0);
- cin.tie(0);
- int n, m;
- cin >> n >> m;
- char mat[n][m];
- bool visited[n][m];
- int si, sj;
- int ei, ej;
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- visited[i][j] = false;
- cin >> mat[i][j];
- if(mat[i][j] == 'A'){
- si = i;
- sj = j;
- }
- if(mat[i][j] == 'B') {
- ei = i;
- ej = j;
- }
- }
- }
- cout << endl;
- queue<int> q;
- q.push(si);
- q.push(sj);
- q.push(0);
- visited[si][sj] = true;
- int di[] = {1, -1, 0, 0};
- int dj[] = {0, 0, 1, -1};
- while(!q.empty()){
- int ci = q.front();
- q.pop();
- int cj = q.front();
- q.pop();
- int dist = q.front();
- q.pop();
- if(mat[ci][cj] == 'B'){
- break;
- }
- for(int i = 0; i < 4; i++){
- if(ci + di[i] < n and ci + di[i] >= 0 and cj + dj[i] < m and cj + dj[i] >= 0 and mat[ci + di[i]][cj + dj[i]] != '#' and !visited[ci + di[i]][cj + dj[i]]){
- q.push(ci + di[i]);
- q.push(cj + dj[i]);
- q.push(dist + 1);
- prev_step[ci + di[i]][cj + dj[i]] = i;
- visited[ci + di[i]][cj + dj[i]] = true;
- }
- }
- }
- if(visited[ei][ej]) {
- cout << "YES" << endl;
- pair<int, int> S = make_pair(si, sj);
- pair<int, int> E = make_pair(ei, ej);
- string result = "";
- while(E != S) {
- int p_cekor = prev_step[E.first][E.second];
- if(p_cekor == 0) {
- result += "D";
- }
- else if(p_cekor == 1) {
- result += "U";
- }
- else if(p_cekor == 2) {
- result += "R";
- }
- else {
- result += "L";
- }
- E = make_pair(E.first - di[p_cekor], E.second - dj[p_cekor]);
- }
- reverse(result.begin(), result.end());
- cout <<result.size() << endl << result << endl;
- }
- else {
- cout << "NO" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement