Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <sstream>
- #include <queue>
- using namespace std;
- class Graph {
- private:
- vector<vector<int> > adj;
- vector<bool> used;
- public:
- Graph(int vertex_count) {
- adj.resize(vertex_count);
- used.resize(vertex_count, false);
- }
- void add_edge(int from, int to) {
- adj[from].push_back(to);
- }
- bool BFS(int start_v, int end_v) {
- queue<int> q;
- q.push(start_v);
- used[start_v] = true;
- while (!q.empty()) {
- int cur_v = q.front();
- q.pop();
- if (cur_v == end_v) {
- return true;
- }
- for (size_t i = 0; i < adj[cur_v].size(); ++i) {
- int nei = adj[cur_v][i];
- if (!used[nei]) {
- q.push(nei);
- used[nei] = true;
- }
- }
- }
- return false;
- }
- };
- class Grid {
- private:
- vector<vector<int> > matrix;
- int rows;
- int cols;
- Graph* graph;
- int index(int x, int y) const {
- return x * cols + y;
- }
- bool is_valid_cell(int x, int y) const {
- return x >= 0 && x < rows && y >= 0 && y < cols;
- }
- public:
- Grid(const vector<vector<int> >& matrix) : matrix(matrix), graph(NULL) {
- rows = matrix.size();
- cols = matrix.empty() ? 0 : matrix[0].size();
- }
- ~Grid() {
- delete graph;
- }
- void build_graph() {
- int vertex_count = rows * cols;
- graph = new Graph(vertex_count);
- int dx[] = { -1, 1, 0, 0 };
- int dy[] = { 0, 0, -1, 1 };
- for (int i = 0; i < rows; ++i) {
- for (int j = 0; j < cols; ++j) {
- if (matrix[i][j] == 1) {
- int from = index(i, j);
- for (int dir = 0; dir < 4; ++dir) {
- int ni = i + dx[dir];
- int nj = j + dy[dir];
- if (is_valid_cell(ni, nj) && matrix[ni][nj] == 1) {
- int to = index(ni, nj);
- graph->add_edge(from, to);
- }
- }
- }
- }
- }
- }
- bool find_path(int start_x, int start_y, int end_x, int end_y) {
- bool start_valid = is_valid_cell(start_x, start_y);
- bool end_valid = is_valid_cell(end_x, end_y);
- if (!start_valid || !end_valid) {
- return false;
- }
- bool start_accessible = (matrix[start_x][start_y] == 1);
- bool end_accessible = (matrix[end_x][end_y] == 1);
- if (!start_accessible || !end_accessible) {
- return false;
- }
- int start_vertex = index(start_x, start_y);
- int end_vertex = index(end_x, end_y);
- return graph->BFS(start_vertex, end_vertex);
- }
- };
- int main() {
- vector<vector<int> > matrix;
- vector<int> coordinates;
- string line;
- while (getline(cin, line)) {
- if (line.empty()) {
- continue;
- }
- vector<int> nums;
- istringstream iss(line);
- int num;
- while (iss >> num) {
- nums.push_back(num);
- }
- if (nums.size() == 2) {
- coordinates.insert(coordinates.end(), nums.begin(), nums.end());
- if (coordinates.size() == 4) {
- break;
- }
- } else if (!nums.empty()) {
- matrix.push_back(nums);
- }
- }
- if (coordinates.size() != 4 || matrix.empty()) {
- cout << "Некорректный ввод" << endl;
- return 0;
- }
- int start_x = coordinates[0] - 1;
- int start_y = coordinates[1] - 1;
- int end_x = coordinates[2] - 1;
- int end_y = coordinates[3] - 1;
- Grid grid(matrix);
- grid.build_graph();
- if (grid.find_path(start_x, start_y, end_x, end_y)) {
- cout << "Дорога есть" << endl;
- } else {
- cout << "Дороги нет" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
