Guest User

Untitled

a guest
Mar 22nd, 2018
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.12 KB | None | 0 0
  1. //
  2. // main.cpp
  3. //
  4. // ******************************
  5. // Рекурсия
  6. // 5. Самый длинный связный кусок
  7. // ******************************
  8. //
  9. // Created by Mikhail Mustakimov on 09.03.2018.
  10. // Copyright © 2018 Mikhail Mustakimov. All rights reserved.
  11. //
  12.  
  13. #include <iostream>
  14. #include <fstream>
  15.  
  16. using namespace std;
  17.  
  18. void readMatrix(ifstream& ifs, short *arr, size_t m, size_t n) {
  19. for (size_t i = 0; i < m; i++) {
  20. for (size_t j = 0; j < n; j++)
  21. ifs >> arr[i * m + j];
  22. }
  23. }
  24.  
  25. void printMatrix(short *arr, size_t m, size_t n) {
  26. for (size_t i = 0; i < m; i++) {
  27. for (size_t j = 0; j < n; j++)
  28. cout << arr[i * m + j] << " ";
  29. cout << endl;
  30. }
  31. }
  32.  
  33. unsigned count(size_t y, size_t x, short *arr, size_t m, size_t n) {
  34. int res = 0;
  35.  
  36. if (arr[y * m + x] == 0)
  37. return 0;
  38.  
  39. if (x < (n - 1) && arr[y * m + (x + 1)]) {
  40. arr[y * m + x] = 0;
  41. res += count(y, x + 1, arr, m, n);
  42. }
  43. if (x > 0 && arr[y * m + (x - 1)]) {
  44. arr[y * m + x] = 0;
  45. res += count(y, x - 1, arr, m, n);
  46. }
  47. if (y < (m - 1) && arr[(y + 1) * m + x]) {
  48. arr[y * m + x] = 0;
  49. res += count(y + 1, x, arr, m, n);
  50. }
  51. if (y > 0 && arr[(y - 1) * m + x]) {
  52. arr[y * m + x] = 0;
  53. res += count(y - 1, x, arr, m, n);
  54. }
  55. arr[y * m + x] = 0;
  56. return res + 1;
  57. }
  58.  
  59. unsigned getLongestWay(short *arr, size_t m, size_t n) {
  60. unsigned res = 0;
  61.  
  62. for (size_t i = 0; i < m; i++) {
  63. for (size_t j = 0; j < n; j++) {
  64. res = max(res, count(i, j, arr, m, n));
  65. // cout << "i=" << i << "; j=" << j << "; res=" << res << endl;
  66. // printMatrix(arr, m, n);
  67. // cout << endl;
  68. }
  69. }
  70. return res;
  71. }
  72.  
  73. int main() {
  74. size_t m, n;
  75.  
  76. ifstream input("input.txt");
  77. ofstream output("output.txt");
  78.  
  79. input >> m >> n;
  80.  
  81. short *arr = new short[m * n];
  82. readMatrix(input, arr, m, n);
  83.  
  84. // printMatrix(arr, m, n);
  85. // cout << endl;
  86.  
  87. output << getLongestWay(arr, m, n);
  88. // printMatrix(arr, m, n);
  89.  
  90. delete[] arr;
  91.  
  92. return 0;
  93. }
Add Comment
Please, Sign In to add comment