API tools faq
paste
Advertisement
coloriot

Ha_27

coloriot
Oct 15th, 2024
20
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.58 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. // Решение задачи про дороги
  6.  
  7. using namespace std;
  8.  
  9. int m, n;
  10. vector< vector<int> > matrix;
  11. vector< vector<bool> > visited;
  12.  
  13. // Функция для разбора строки входных данных на целые числа
  14. void parseLine(const string& line, vector<int>& nums) {
  15.     int num = 0;
  16.     bool inNum = false;
  17.     for (size_t i = 0; i < line.size(); ++i) {
  18.         char c = line[i];
  19.         if (c >= '0' && c <= '9') {
  20.             num = num * 10 + (c - '0');
  21.             inNum = true;
  22.         } else if (inNum) {
  23.             nums.push_back(num);
  24.             num = 0;
  25.             inNum = false;
  26.         }
  27.     }
  28.     if (inNum) {
  29.         nums.push_back(num);
  30.     }
  31. }
  32.  
  33. bool dfs(int x, int y, int dest_x, int dest_y) {
  34.     if (x == dest_x && y == dest_y) {
  35.         return true;
  36.     }
  37.     visited[x][y] = true;
  38.  
  39.     // Векторы направления: вверх, вниз, влево, вправо
  40.     int dx[] = {-1, 1, 0, 0};
  41.     int dy[] = {0, 0, -1, 1};
  42.  
  43.     for (int dir = 0; dir < 4; dir++) {
  44.         int nx = x + dx[dir];
  45.         int ny = y + dy[dir];
  46.  
  47.     // Проверяем нахождение новой позции
  48.         if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
  49.             !visited[nx][ny] && matrix[nx][ny] == 1) {
  50.             if (dfs(nx, ny, dest_x, dest_y)) {
  51.                 return true;
  52.             }
  53.         }
  54.     }
  55.     return false;
  56. }
  57.  
  58. int main() {
  59.     string line;
  60.     vector<int> row;
  61.  
  62.     if (!getline(cin, line)) {
  63.         cout << "Некорректный ввод" << endl;
  64.         return 0;
  65.     }
  66.     parseLine(line, row);
  67.     if (row.empty()) {
  68.         cout << "Некорректный ввод" << endl;
  69.         return 0;
  70.     }
  71.     n = row.size();
  72.     matrix.push_back(row);
  73.  
  74.     while (getline(cin, line)) {
  75.         vector<int> nums;
  76.         parseLine(line, nums);
  77.  
  78.         if (nums.size() == 2) {
  79.             m = matrix.size();
  80.             int i1 = nums[0];
  81.             int j1 = nums[1];
  82.  
  83.             if (!getline(cin, line)) {
  84.                 cout << "Некорректный ввод" << endl;
  85.                 return 0;
  86.             }
  87.             vector<int> nums2;
  88.             parseLine(line, nums2);
  89.             if (nums2.size() != 2) {
  90.                 cout << "Некорректный ввод" << endl;
  91.                 return 0;
  92.             }
  93.             int i2 = nums2[0];
  94.             int j2 = nums2[1];
  95.  
  96.             visited.resize(m, vector<bool>(n, false));
  97.  
  98.             // Меняем индексы с 1-го на 0-й
  99.             int start_x = i1 - 1;
  100.             int start_y = j1 - 1;
  101.             int dest_x = i2 - 1;
  102.             int dest_y = j2 - 1;
  103.  
  104.             if (start_x < 0 || start_x >= m || start_y < 0 || start_y >= n ||
  105.                 dest_x < 0 || dest_x >= m || dest_y < 0 || dest_y >= n ||
  106.                 matrix[start_x][start_y] == 0 || matrix[dest_x][dest_y] == 0) {
  107.                 cout << "Дороги нет" << endl;
  108.                 return 0;
  109.             }
  110.  
  111.             if (dfs(start_x, start_y, dest_x, dest_y)) {
  112.                 cout << "Дорога есть" << endl;
  113.             } else {
  114.                 cout << "Дороги нет" << endl;
  115.             }
  116.  
  117.             return 0;
  118.  
  119.         } else if (nums.size() == n) {
  120.             matrix.push_back(nums);
  121.         } else {
  122.             cout << "Некорректный ввод" << endl;
  123.             return 0;
  124.         }
  125.     }
  126.  
  127.     cout << "Некорректный ввод" << endl;
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!