Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- //
- // ******************************
- // Рекурсия
- // 5. Самый длинный связный кусок
- // ******************************
- //
- // Created by Mikhail Mustakimov on 09.03.2018.
- // Copyright © 2018 Mikhail Mustakimov. All rights reserved.
- //
- #include <iostream>
- #include <fstream>
- using namespace std;
- void readMatrix(ifstream& ifs, short *arr, size_t m, size_t n) {
- for (size_t i = 0; i < m; i++) {
- for (size_t j = 0; j < n; j++)
- ifs >> arr[i * m + j];
- }
- }
- void printMatrix(short *arr, size_t m, size_t n) {
- for (size_t i = 0; i < m; i++) {
- for (size_t j = 0; j < n; j++)
- cout << arr[i * m + j] << " ";
- cout << endl;
- }
- }
- unsigned count(size_t y, size_t x, short *arr, size_t m, size_t n) {
- int res = 0;
- if (arr[y * m + x] == 0)
- return 0;
- if (x < (n - 1) && arr[y * m + (x + 1)]) {
- arr[y * m + x] = 0;
- res += count(y, x + 1, arr, m, n);
- }
- if (x > 0 && arr[y * m + (x - 1)]) {
- arr[y * m + x] = 0;
- res += count(y, x - 1, arr, m, n);
- }
- if (y < (m - 1) && arr[(y + 1) * m + x]) {
- arr[y * m + x] = 0;
- res += count(y + 1, x, arr, m, n);
- }
- if (y > 0 && arr[(y - 1) * m + x]) {
- arr[y * m + x] = 0;
- res += count(y - 1, x, arr, m, n);
- }
- arr[y * m + x] = 0;
- return res + 1;
- }
- unsigned getLongestWay(short *arr, size_t m, size_t n) {
- unsigned res = 0;
- for (size_t i = 0; i < m; i++) {
- for (size_t j = 0; j < n; j++) {
- res = max(res, count(i, j, arr, m, n));
- // cout << "i=" << i << "; j=" << j << "; res=" << res << endl;
- // printMatrix(arr, m, n);
- // cout << endl;
- }
- }
- return res;
- }
- int main() {
- size_t m, n;
- ifstream input("input.txt");
- ofstream output("output.txt");
- input >> m >> n;
- short *arr = new short[m * n];
- readMatrix(input, arr, m, n);
- // printMatrix(arr, m, n);
- // cout << endl;
- output << getLongestWay(arr, m, n);
- // printMatrix(arr, m, n);
- delete[] arr;
- return 0;
- }
Add Comment
Please, Sign In to add comment