Advertisement
add1ctus

Бомбардер

Mar 9th, 2016
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <utility>
  3. #include <queue>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. struct state
  9. {
  10. int x;
  11. int y;
  12. int b;
  13.  
  14. state(int xx, int yy, int bb)
  15. {
  16. x = xx;
  17. y = yy;
  18. b = bb;
  19. }
  20. };
  21.  
  22. int xd[] = {0,0,1,-1};
  23. int yd[] = {1,-1,0,0};
  24.  
  25. bool visited[50][50][100];
  26. int dist[50][50][100];
  27.  
  28. int main()
  29. {
  30. ios_base::sync_with_stdio(false);
  31. cin.tie(0);
  32. int n, bombs;
  33. cin>>n;
  34. string mapa[n];
  35.  
  36. pair<int, int> start;
  37. pair<int, int> finish;
  38.  
  39. for(int i = 0 ; i < n ; ++i)
  40. {
  41. cin>>mapa[i];
  42. for(int j = 0 ; j < mapa[0].size() ; ++j)
  43. {
  44. if(mapa[i][j] == 'B')
  45. start = make_pair(i,j);
  46. else if(mapa[i][j] == 'E')
  47. finish = make_pair(i,j);
  48. }
  49. }
  50.  
  51. cin>>bombs;
  52.  
  53. visited[start.first][start.second][0] = true;
  54. queue<state> Q;
  55. Q.push(state(start.first,start.second,0));
  56.  
  57. while(!Q.empty())
  58. {
  59. state curr = Q.front();
  60. Q.pop();
  61.  
  62. if(curr.x == finish.first && curr.y == finish.second)
  63. {
  64. dist[curr.x][curr.y][curr.b];
  65. return 0;
  66. }
  67.  
  68. for(int i = 0 ; i < 4 ; ++i)
  69. {
  70. int x = curr.x + xd[i];
  71. int y = curr.y + yd[i];
  72. if(x >= 0 && x < n && y >= 0 && y < mapa[0].size())
  73. {
  74. if(mapa[x][y] == '#' && curr.b < bombs && !visited[x][y][curr.b+1])
  75. {
  76. dist[x][y][curr.b+1] = dist[curr.x][curr.y][curr.b] + 3;
  77. Q.push(state(x,y,curr.b+1));
  78. visited[x][y][curr.b+1] = true;
  79. }
  80. else if(mapa[x][y] != '#' && !visited[x][y][curr.b])
  81. {
  82. dist[x][y][curr.b] = dist[curr.x][curr.y][curr.b] + 1;
  83. Q.push(state(x,y,curr.b));
  84. visited[x][y][curr.b] = true;
  85. }
  86. }
  87. }
  88. }
  89.  
  90. cout<<-1;
  91.  
  92. return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement