Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <climits>
- #include <cstdint>
- #include <iomanip>
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- struct Point
- {
- int x;
- int y;
- };
- bool operator==(const Point& lhs, const Point& rhs)
- {
- return tie(lhs.x, lhs.y) == tie(rhs.x, rhs.y);
- }
- Point GetNewPoint(const vector< vector< int > >& field, int x, int y, int dx, int dy)
- {
- while (field[x + dx][y + dy] == 0)
- {
- x += dx;
- y += dy;
- }
- if (field[x + dx][y + dy] == 2)
- {
- x += dx;
- y += dy;
- }
- return { x, y };
- }
- int32_t GetMinMovesCount(const vector< vector< int > >& field)
- {
- vector< vector< bool > > is_visited(field.size(), vector< bool >(field.front().size(), false));
- int x_starting_pos = 1;
- int y_starting_pos = 1;
- is_visited[x_starting_pos][y_starting_pos] = true;
- queue< pair< Point, int > > q;
- q.push({ { x_starting_pos, y_starting_pos }, 0 });
- while (!q.empty())
- {
- Point cur_point = q.front().first;
- int x = cur_point.x;
- int y = cur_point.y;
- int moves_count = q.front().second;
- q.pop();
- if (field[x][y] == 2)
- {
- return moves_count;
- }
- for (int dx = -1; dx <= 1; ++dx)
- {
- for (int dy = -1; dy <= 1; ++dy)
- {
- if (dx * dx + dy * dy != 1)
- continue;
- Point new_point = GetNewPoint(field, x, y, dx, dy);
- if (is_visited[new_point.x][new_point.y])
- continue;
- q.push({ new_point, moves_count + 1 });
- is_visited[new_point.x][new_point.y] = true;
- }
- }
- }
- }
- int main()
- {
- int32_t rows_count, columns_count;
- cin >> rows_count >> columns_count;
- vector< vector< int32_t > > field(rows_count + 2, vector< int >(columns_count + 2, INT32_MAX));
- for (int32_t i = 1; i < field.size() - 1; ++i)
- {
- for (int32_t j = 1; j < field.front().size() - 1; ++j)
- {
- cin >> field[i][j];
- }
- }
- cout << GetMinMovesCount(field);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement