Advertisement
Guest User

Untitled

a guest
Aug 27th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. #define x first
  6. #define y second
  7. #define pb push_back
  8.  
  9. using namespace std;
  10.  
  11. const int dx[4] = {-1,0,1,0};
  12. const int dy[4] = {0,1,0,-1};
  13. int n,m;
  14. const int INF = 1000000000;
  15.  
  16. bool is_correct(int x,int y){
  17. return x >= 0 && x < n && y >= 0 && y < m;
  18. }
  19.  
  20. int main()
  21. {
  22. cin >> n >> m;
  23. vector<vector<int>> g(n,vector<int> (m));
  24. vector<vector<bool>> used(n,vector<bool>(m));
  25. vector <vector<int>> dist(n,vector<int> (m,INF));
  26. dist[0][0] = 0;
  27. used[0][0] = true;
  28. for (int i = 0; i < n; i++)
  29. for (int j = 0; j < m; j++){
  30. cin >> g[i][j];
  31. if (g[i][j] == 1)
  32. used[i][j] = 1;
  33. }
  34. queue<pair<int,int>> q;
  35. q.push({0,0});
  36.  
  37. while (!q.empty()){
  38. auto p = q.front();
  39. q.pop();
  40. for (int i = 0; i < 4; i++){
  41. int x = p.x + dx[i];
  42. int y = p.x + dy[i];
  43. while (is_correct(x,y) && g[x][y] == 0){
  44. x += dx[i];
  45. y += dy[i];
  46. }
  47. if (!is_correct(x,y)){
  48. x -= dx[i];
  49. y -= dy[i];
  50. }
  51. if (g[x][y] == 2){
  52. cout << dist[p.x][p.y] + 1 << endl;
  53. return 0;
  54. }
  55. if (!used[x][y]){
  56. q.push({x,y});
  57. used[x][y] = true;
  58. dist[x][y] = dist[p.x][p.y] + 1;
  59. }
  60. }
  61. }
  62. return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement