HA_29

coloriot

Nov 8th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 4.22 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
vector<vector<int> > adj;
vector<bool> used;
vector<vector<int> > matrix;
int rows, cols;
int original_value;
int new_value;
public:
Graph(int vertex_count, const vector<vector<int> >& input_matrix) {
adj.resize(vertex_count);
used.resize(vertex_count, false);
matrix = input_matrix;
rows = matrix.size();
cols = matrix[0].size();
}
void add_edge(int from, int to) {
adj[from].push_back(to);
}
void build_graph() {
int dx[] = { -1, 1, 0, 0 }; // вверх, вниз
int dy[] = { 0, 0, -1, 1 }; // влево, вправо
for (int x = 0; x < rows; ++x) {
for (int y = 0; y < cols; ++y) {
int from = x * cols + y;
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
int to = nx * cols + ny;
add_edge(from, to);
}
}
}
}
}
void flood_fill(int x, int y, int new_value) {
int start_v = x * cols + y;
this->new_value = new_value;
original_value = matrix[x][y];
if (original_value == new_value) {
return;
}
BFS(start_v);
}
bool BFS(int start_v) {
queue<int> q;
q.push(start_v);
used[start_v] = true;
matrix[start_v / cols][start_v % cols] = new_value;
while (!q.empty()) {
int cur_v = q.front();
q.pop();
for (size_t i = 0; i < adj[cur_v].size(); ++i) {
int nei = adj[cur_v][i];
if (!used[nei]) {
int nx = nei / cols;
int ny = nei % cols;
if (matrix[nx][ny] == original_value) {
q.push(nei);
used[nei] = true;
matrix[nx][ny] = new_value;
}
}
}
}
return false;
}
void print_matrix() const {
for (size_t i = 0; i < matrix.size(); ++i) {
const vector<int>& row = matrix[i];
for (size_t j = 0; j < row.size(); ++j) {
cout << row[j];
if (j < row.size() - 1) {
cout << " ";
}
}
cout << endl;
}
}
};
int main() {
vector<vector<int> > matrix;
string line;
int start_x = -1, start_y = -1, new_value = -1;
while (getline(cin, line)) {
if (line.empty()) {
continue;
}
vector<int> nums;
size_t pos = 0;
while (pos < line.size()) {
// Пропуск пробелов и табуляций
while (pos < line.size() && (line[pos] == ' ' || line[pos] == '\t')) {
++pos;
}
// Сборка числа
int num = 0;
bool found = false;
while (pos < line.size() && isdigit(line[pos])) {
num = num * 10 + (line[pos] - '0');
++pos;
found = true;
}
if (found) {
nums.push_back(num);
} else {
++pos;
}
}
if (nums.empty()) {
continue;
}
if (nums.size() == 3 && start_x == -1) {
start_x = nums[0] - 1;
start_y = nums[1] - 1;
new_value = nums[2];
break;
} else {
matrix.push_back(nums);
}
}
if (start_x == -1 || matrix.empty()) {
cout << "Некорректный ввод" << endl;
return 0;
}
int vertex_count = matrix.size() * matrix[0].size();
Graph graph(vertex_count, matrix);
graph.build_graph();
graph.flood_fill(start_x, start_y, new_value);
graph.print_matrix();
return 0;
}

Add Comment

Please, Sign In to add comment