API tools faq
paste
Advertisement
coloriot

HA_28_2

coloriot
Oct 25th, 2024
18
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.37 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. class Graph {
  8. private:
  9.     vector< vector<int> > adj;
  10.     vector<bool> visited;
  11.  
  12. public:
  13.     Graph(int vertex_count) {
  14.         adj.resize(vertex_count);
  15.         visited.resize(vertex_count, false);
  16.     }
  17.  
  18.     void add_edge(int from, int to) {
  19.         adj[from].push_back(to);
  20.     }
  21.  
  22.     void BFS(int start_v, int original_value, int new_value, vector< vector<int> >& matrix, int cols) {
  23.         queue<int> q;
  24.         q.push(start_v);
  25.         visited[start_v] = true;
  26.  
  27.         while (!q.empty()) {
  28.             int cur_v = q.front();
  29.             q.pop();
  30.  
  31.             int x = cur_v / cols;
  32.             int y = cur_v % cols;
  33.  
  34.             matrix[x][y] = new_value;
  35.  
  36.             for (size_t i = 0; i < adj[cur_v].size(); ++i) {
  37.                 int nei = adj[cur_v][i];
  38.                 if (!visited[nei]) {
  39.                     int nx = nei / cols;
  40.                     int ny = nei % cols;
  41.                     if (matrix[nx][ny] == original_value) {
  42.                         q.push(nei);
  43.                         visited[nei] = true;
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.     }
  49. };
  50.  
  51. class Grid {
  52. private:
  53.     vector< vector<int> > matrix;
  54.     int rows;
  55.     int cols;
  56.     Graph* graph;
  57.  
  58.     int index(int x, int y) const {
  59.         return x * cols + y;
  60.     }
  61.  
  62.     bool is_valid_cell(int x, int y) const {
  63.         return x >= 0 && x < rows && y >= 0 && y < cols;
  64.     }
  65.  
  66. public:
  67.     Grid(const vector< vector<int> >& input_matrix) : matrix(input_matrix), graph(NULL) {
  68.         rows = matrix.size();
  69.         cols = matrix.empty() ? 0 : matrix[0].size();
  70.     }
  71.  
  72.     ~Grid() {
  73.         delete graph;
  74.     }
  75.  
  76.     void build_graph() {
  77.         int total_vertices = rows * cols;
  78.         graph = new Graph(total_vertices);
  79.  
  80.         int dx[] = { -1, 1, 0, 0 };
  81.         int dy[] = { 0, 0, -1, 1 };
  82.  
  83.         for (int x = 0; x < rows; ++x) {
  84.             for (int y = 0; y < cols; ++y) {
  85.                 int from = index(x, y);
  86.                 for (int dir = 0; dir < 4; ++dir) {
  87.                     int nx = x + dx[dir];
  88.                     int ny = y + dy[dir];
  89.                     if (is_valid_cell(nx, ny)) {
  90.                         int to = index(nx, ny);
  91.                         graph->add_edge(from, to);
  92.                     }
  93.                 }
  94.             }
  95.         }
  96.     }
  97.  
  98.     void flood_fill(int x, int y, int new_value) {
  99.         if (!is_valid_cell(x, y)) {
  100.             return;
  101.         }
  102.  
  103.         int original_value = matrix[x][y];
  104.         if (original_value == new_value) {
  105.             return;
  106.         }
  107.  
  108.         int start_vertex = index(x, y);
  109.         graph->BFS(start_vertex, original_value, new_value, matrix, cols);
  110.     }
  111.  
  112.     void print_matrix() const {
  113.         for (int i = 0; i < rows; ++i) {
  114.             for (int j = 0; j < cols; ++j) {
  115.                 cout << matrix[i][j];
  116.                 if (j < cols - 1) {
  117.                     cout << " ";
  118.                 }
  119.             }
  120.             cout << endl;
  121.         }
  122.     }
  123. };
  124.  
  125. int main() {
  126.     vector< vector<int> > matrix;
  127.     string line;
  128.     int start_x = -1, start_y = -1, new_value = -1;
  129.  
  130.     while (getline(cin, line)) {
  131.         if (line.empty()) {
  132.             continue;
  133.         }
  134.  
  135.         vector<int> nums;
  136.         int num = 0;
  137.         bool in_number = false;
  138.  
  139.         for (size_t i = 0; i <= line.length(); ++i) {
  140.             if (i < line.length() && line[i] >= '0' && line[i] <= '9') {
  141.                 num = num * 10 + (line[i] - '0');
  142.                 in_number = true;
  143.             } else {
  144.                 if (in_number) {
  145.                     nums.push_back(num);
  146.                     num = 0;
  147.                     in_number = false;
  148.                 }
  149.             }
  150.         }
  151.  
  152.         if (nums.empty()) {
  153.             continue;
  154.         }
  155.  
  156.         if (nums.size() == 3 && start_x == -1) {
  157.             start_x = nums[0] - 1;
  158.             start_y = nums[1] - 1;
  159.             new_value = nums[2];
  160.             break;
  161.         } else {
  162.             matrix.push_back(nums);
  163.         }
  164.     }
  165.  
  166.     if (start_x == -1 || matrix.empty()) {
  167.         cout << "Некорректный ввод" << endl;
  168.         return 0;
  169.     }
  170.  
  171.     Grid grid(matrix);
  172.     grid.build_graph();
  173.     grid.flood_fill(start_x, start_y, new_value);
  174.     grid.print_matrix();
  175.  
  176.     return 0;
  177. }
  178.  
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!