Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define inrep int t; cin >> t; for(int tc=1; tc<=t; tc++)
- #define fi first
- #define sc second
- #define mp make_pair
- int main()
- {
- int n, m; cin >> n >> m; string s[n+8];
- pair<int, int> safe, rusa;
- for(int i=0; i<n; i++) {
- cin >> s[i];
- for(int j=0; j<n; j++) {
- if (s[i][j] == 'S')
- safe.fi = i, safe.sc = j;
- else if (s[i][j] == 'R')
- rusa.fi = i, rusa.sc = j;
- }
- }
- queue<pair<pair<int, pair<int, int> >, int > > q;
- q.push(mp(mp(m, mp(rusa.fi, rusa.sc)), 0));
- bool vis[1007][1007] = {0};
- int f = 0;
- while(q.size())
- {
- int x = q.front().fi.sc.fi, y = q.front().fi.sc.sc; int bats = q.front().fi.fi, hit = q.front().sc; q.pop();
- if (x < 0 || x >= n || y < 0 || y >= n) continue;
- if (x == safe.fi && y == safe.sc) {
- cout << hit << "\n";
- f = 1;
- break;
- }
- if (s[x][y-1] == '#' && bats > 0)
- q.push(mp(mp(bats-1, mp(x, y-1)), hit+1));
- else if (vis[x][y-1] == 0 && s[x][y-1] != '#')
- vis[x][y-1] = 1,
- q.push(mp(mp(bats, mp(x, y-1)), hit+1));
- if (s[x+1][y] == '#' && bats > 0)
- q.push(mp(mp(bats-1, mp(x+1, y)), hit+1));
- else if (vis[x+1][y] == 0 && s[x+1][y] != '#')
- vis[x+1][y] = 1,
- q.push(mp(mp(bats, mp(x+1, y)), hit+1));
- if (s[x][y+1] == '#' && bats > 0)
- q.push(mp(mp(bats-1, mp(x, y+1)), hit+1));
- else if (vis[x][y+1] == 0 && s[x][y+1] != '#')
- vis[x][y+1] = 1,
- q.push(mp(mp(bats, mp(x, y+1)), hit+1));
- if (s[x-1][y] == '#' && bats > 0)
- q.push(mp(mp(bats-1, mp(x-1, y)), hit+1));
- else if (vis[x-1][y] == 0 && s[x-1][y] != '#')
- vis[x-1][y] = 1,
- q.push(mp(mp(bats, mp(x-1, y)), hit+1));
- }
- if (f == 0) {
- cout << "IMPOSSIBLE" << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement