Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- vector<int> returnPosibbleMoves(const vector<vector<char>>& map, const int& v, const int& M, const int& N) {
- int x = v % M;
- vector<int> temp;
- int y = v / M;
- if (y == 0) {
- if (x == 0) {
- if (map[y][x + 1] != '+')
- temp.push_back(y * M + x + 1);
- if (map[y + 1][x] != '+')
- temp.push_back(y * M + x + M);
- } else if (x == M - 1) {
- if (map[y + 1][x] != '+')
- temp.push_back(y * M + x + M);
- if (map[y][x - 1] != '+')
- temp.push_back(y * M + x - 1);
- } else {
- if (map[y + 1][x] != '+')
- temp.push_back(y * M + x + M);
- if (map[y][x - 1] != '+')
- temp.push_back(y * M + x - 1);
- if (map[y][x + 1] != '+')
- temp.push_back(y * M + x + 1);
- }
- } else if (y == N - 1) {
- if (x == 0) {
- if (map[y][x + 1] != '+')
- temp.push_back(y * M + x + 1);
- if (map[y - 1][x] != '+')
- temp.push_back(y * M + x - M);
- } else if (x == M - 1) {
- if (map[y - 1][x] != '+')
- temp.push_back(y * M + x - M);
- if (map[y][x - 1] != '+')
- temp.push_back(y * M + x - 1);
- } else {
- if (map[y][x - 1] != '+')
- temp.push_back(y * M + x - 1);
- if (map[y][x + 1] != '+')
- temp.push_back(y * M + x + 1);
- if (map[y - 1][x] != '+')
- temp.push_back(y * M + x - M);
- }
- } else if (x == 0) {
- if (map[y + 1][x] != '+')
- temp.push_back(y * M + x + M);
- if (map[y][x + 1] != '+')
- temp.push_back(y * M + x + 1);
- if (map[y - 1][x] != '+')
- temp.push_back(y * M + x - M);
- } else if (x == M - 1) {
- if (map[y + 1][x] != '+')
- temp.push_back(y * M + x + M);
- if (map[y][x - 1] != '+')
- temp.push_back(y * M + x - 1);
- if (map[y - 1][x] != '+')
- temp.push_back(y * M + x - M);
- } else {
- if (map[y][x + 1] != '+')
- temp.push_back(y * M + x + 1);
- if (map[y + 1][x] != '+')
- temp.push_back(y * M + x + M);
- if (map[y][x - 1] != '+')
- temp.push_back(y * M + x - 1);
- if (map[y - 1][x] != '+')
- temp.push_back(y * M + x - M);
- }
- return temp;
- }
- int main() {
- int N, M;
- cin >> N >> M;
- vector<vector<char>> map(N);
- for (int i = 0; i < N; ++i) {
- map[i].resize(M);
- }
- int s = 0, f = 0; //start and finish
- for (int i = 0; i < N; ++i) {
- for (int j = 0; j < M; ++j) {
- cin >> map[i][j];
- if (map[i][j] == '@')
- s = i * M + j;
- else if (map[i][j] == '#')
- f = i * M + j;
- }
- }
- bool a = false;
- queue<int> q;
- q.push(s);
- vector<bool> used(N * M);
- vector<int> d(N * M);
- used[s] = true;
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- vector<int> temp = returnPosibbleMoves(map, v, M, N);
- for (unsigned long int i = 0; i < temp.size(); ++i) {
- int to = temp[i];
- if (!used[to]) {
- used[to] = true;
- q.push(to);
- d[to] = d[v] + 1;
- if (to == f) {
- a = true;
- cout << d[to];
- }
- }
- }
- }
- if (!a)
- cout << -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement