Advertisement
Guest User

Untitled

a guest
Jan 21st, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define inrep int t; cin >> t; for(int tc=1; tc<=t; tc++)
  5.  
  6. #define fi first
  7. #define sc second
  8. #define mp make_pair
  9.  
  10. int main()
  11. {
  12. int n, m; cin >> n >> m; string s[n+8];
  13. pair<int, int> safe, rusa;
  14. for(int i=0; i<n; i++) {
  15. cin >> s[i];
  16. for(int j=0; j<n; j++) {
  17. if (s[i][j] == 'S')
  18. safe.fi = i, safe.sc = j;
  19. else if (s[i][j] == 'R')
  20. rusa.fi = i, rusa.sc = j;
  21. }
  22. }
  23. queue<pair<pair<int, pair<int, int> >, int > > q;
  24. q.push(mp(mp(m, mp(rusa.fi, rusa.sc)), 0));
  25. bool vis[1007][1007] = {0};
  26. int f = 0;
  27. while(q.size())
  28. {
  29. 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();
  30.  
  31. if (x < 0 || x >= n || y < 0 || y >= n) continue;
  32.  
  33. if (x == safe.fi && y == safe.sc) {
  34. cout << hit << "\n";
  35. f = 1;
  36. break;
  37. }
  38.  
  39. if (s[x][y-1] == '#' && bats > 0)
  40. q.push(mp(mp(bats-1, mp(x, y-1)), hit+1));
  41. else if (vis[x][y-1] == 0 && s[x][y-1] != '#')
  42. vis[x][y-1] = 1,
  43. q.push(mp(mp(bats, mp(x, y-1)), hit+1));
  44.  
  45. if (s[x+1][y] == '#' && bats > 0)
  46. q.push(mp(mp(bats-1, mp(x+1, y)), hit+1));
  47. else if (vis[x+1][y] == 0 && s[x+1][y] != '#')
  48. vis[x+1][y] = 1,
  49. q.push(mp(mp(bats, mp(x+1, y)), hit+1));
  50.  
  51. if (s[x][y+1] == '#' && bats > 0)
  52. q.push(mp(mp(bats-1, mp(x, y+1)), hit+1));
  53. else if (vis[x][y+1] == 0 && s[x][y+1] != '#')
  54. vis[x][y+1] = 1,
  55. q.push(mp(mp(bats, mp(x, y+1)), hit+1));
  56.  
  57. if (s[x-1][y] == '#' && bats > 0)
  58. q.push(mp(mp(bats-1, mp(x-1, y)), hit+1));
  59. else if (vis[x-1][y] == 0 && s[x-1][y] != '#')
  60. vis[x-1][y] = 1,
  61. q.push(mp(mp(bats, mp(x-1, y)), hit+1));
  62. }
  63. if (f == 0) {
  64. cout << "IMPOSSIBLE" << "\n";
  65. }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement