HA_28_2

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
private:
    vector< vector<int> > adj;
    vector<bool> visited;

public:
    Graph(int vertex_count) {
        adj.resize(vertex_count);
        visited.resize(vertex_count, false);
    }

    void add_edge(int from, int to) {
        adj[from].push_back(to);
    }

    void BFS(int start_v, int original_value, int new_value, vector< vector<int> >& matrix, int cols) {
        queue<int> q;
        q.push(start_v);
        visited[start_v] = true;

        while (!q.empty()) {
            int cur_v = q.front();
            q.pop();

            int x = cur_v / cols;
            int y = cur_v % cols;

            matrix[x][y] = new_value;

            for (size_t i = 0; i < adj[cur_v].size(); ++i) {
                int nei = adj[cur_v][i];
                if (!visited[nei]) {
                    int nx = nei / cols;
                    int ny = nei % cols;
                    if (matrix[nx][ny] == original_value) {
                        q.push(nei);
                        visited[nei] = true;
                    }
                }
            }
        }
    }
};

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> >& input_matrix) : matrix(input_matrix), graph(NULL) {
        rows = matrix.size();
        cols = matrix.empty() ? 0 : matrix[0].size();
    }

    ~Grid() {
        delete graph;
    }

    void build_graph() {
        int total_vertices = rows * cols;
        graph = new Graph(total_vertices);

        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 = index(x, y);
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (is_valid_cell(nx, ny)) {
                        int to = index(nx, ny);
                        graph->add_edge(from, to);
                    }
                }
            }
        }
    }

    void flood_fill(int x, int y, int new_value) {
        if (!is_valid_cell(x, y)) {
            return;
        }

        int original_value = matrix[x][y];
        if (original_value == new_value) {
            return;
        }

        int start_vertex = index(x, y);
        graph->BFS(start_vertex, original_value, new_value, matrix, cols);
    }

    void print_matrix() const {
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                cout << matrix[i][j];
                if (j < cols - 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;
        int num = 0;
        bool in_number = false;

        for (size_t i = 0; i <= line.length(); ++i) {
            if (i < line.length() && line[i] >= '0' && line[i] <= '9') {
                num = num * 10 + (line[i] - '0');
                in_number = true;
            } else {
                if (in_number) {
                    nums.push_back(num);
                    num = 0;
                    in_number = false;
                }
            }
        }

        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;
    }

    Grid grid(matrix);
    grid.build_graph();
    grid.flood_fill(start_x, start_y, new_value);
    grid.print_matrix();

    return 0;
}