Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. vector<int> returnPosibbleMoves(const vector<vector<char>>& map, const int& v, const int& M, const int& N) {
  7.   int x = v % M;
  8.   vector<int> temp;
  9.   int y = v / M;
  10.   if (y == 0) {
  11.     if (x == 0) {
  12.       if (map[y][x + 1] != '+')
  13.         temp.push_back(y * M + x + 1);
  14.       if (map[y + 1][x] != '+')
  15.         temp.push_back(y * M + x + M);
  16.     } else if (x == M - 1) {
  17.       if (map[y + 1][x] != '+')
  18.         temp.push_back(y * M + x + M);
  19.       if (map[y][x - 1] != '+')
  20.         temp.push_back(y * M + x - 1);
  21.     } else {
  22.       if (map[y + 1][x] != '+')
  23.         temp.push_back(y * M + x + M);
  24.       if (map[y][x - 1] != '+')
  25.         temp.push_back(y * M + x - 1);
  26.       if (map[y][x + 1] != '+')
  27.         temp.push_back(y * M + x + 1);
  28.     }
  29.   } else if (y == N - 1) {
  30.     if (x == 0) {
  31.       if (map[y][x + 1] != '+')
  32.         temp.push_back(y * M + x + 1);
  33.       if (map[y - 1][x] != '+')
  34.         temp.push_back(y * M + x - M);
  35.     } else if (x == M - 1) {
  36.       if (map[y - 1][x] != '+')
  37.         temp.push_back(y * M + x - M);
  38.       if (map[y][x - 1] != '+')
  39.         temp.push_back(y * M + x - 1);
  40.     } else {
  41.       if (map[y][x - 1] != '+')
  42.         temp.push_back(y * M + x - 1);
  43.       if (map[y][x + 1] != '+')
  44.         temp.push_back(y * M + x + 1);
  45.       if (map[y - 1][x] != '+')
  46.         temp.push_back(y * M + x - M);
  47.     }
  48.   } else if (x == 0) {
  49.     if (map[y + 1][x] != '+')
  50.       temp.push_back(y * M + x + M);
  51.     if (map[y][x + 1] != '+')
  52.       temp.push_back(y * M + x + 1);
  53.     if (map[y - 1][x] != '+')
  54.       temp.push_back(y * M + x - M);
  55.   } else if (x == M - 1) {
  56.     if (map[y + 1][x] != '+')
  57.       temp.push_back(y * M + x + M);
  58.     if (map[y][x - 1] != '+')
  59.       temp.push_back(y * M + x - 1);
  60.     if (map[y - 1][x] != '+')
  61.       temp.push_back(y * M + x - M);
  62.   } else {
  63.     if (map[y][x + 1] != '+')
  64.       temp.push_back(y * M + x + 1);
  65.     if (map[y + 1][x] != '+')
  66.       temp.push_back(y * M + x + M);
  67.     if (map[y][x - 1] != '+')
  68.       temp.push_back(y * M + x - 1);
  69.     if (map[y - 1][x] != '+')
  70.       temp.push_back(y * M + x - M);
  71.   }
  72.   return temp;
  73. }
  74.  
  75. int main() {
  76.   int N, M;
  77.   cin >> N >> M;
  78.   vector<vector<char>> map(N);
  79.   for (int i = 0; i < N; ++i) {
  80.     map[i].resize(M);
  81.   }
  82.   int s = 0, f = 0; //start and finish
  83.  
  84.   for (int i = 0; i < N; ++i) {
  85.     for (int j = 0; j < M; ++j) {
  86.       cin >> map[i][j];
  87.       if (map[i][j] == '@')
  88.         s = i * M + j;
  89.       else if (map[i][j] == '#')
  90.         f = i * M + j;
  91.     }
  92.   }
  93.  
  94.   bool a = false;
  95.  
  96.   queue<int> q;
  97.   q.push(s);
  98.   vector<bool> used(N * M);
  99.   vector<int> d(N * M);
  100.   used[s] = true;
  101.   while (!q.empty()) {
  102.     int v = q.front();
  103.     q.pop();
  104.     vector<int> temp = returnPosibbleMoves(map, v, M, N);
  105.     for (unsigned long int i = 0; i < temp.size(); ++i) {
  106.       int to = temp[i];
  107.       if (!used[to]) {
  108.         used[to] = true;
  109.         q.push(to);
  110.         d[to] = d[v] + 1;
  111.         if (to == f) {
  112.           a = true;
  113.           cout << d[to];
  114.         }
  115.       }
  116.     }
  117.   }
  118.  
  119.   if (!a)
  120.     cout << -1;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement