Advertisement
Guest User

Untitled

a guest
Apr 25th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4. int k, n;
  5. cin >> n >> k;
  6. int a[n][n];
  7. int a1[n][n];
  8. int a2[n][n];
  9. int b[n][n];
  10. int c[n][n];
  11. string s;
  12. for (int i = 0; i < n; i++) {
  13. cin >> s;
  14. for (int j = 0; j < n; j++)
  15. if (s[j] == '#') {
  16. a[i][j] = 0;
  17. a1[i][j] = 0;
  18. a2[i][j] = 0;
  19. b[i][j] = 0;
  20. c[i][j] = 0;
  21. } else {
  22. a[i][j] = 1;
  23. a1[i][j] = 1;
  24. a2[i][j] = 1;
  25. b[i][j] = 0;
  26. c[i][j] = 0;
  27. }
  28. };
  29. for (int i = 0; i < n; i++)
  30. for (int j = 0; j < n; j++) {
  31. if (a1[i][j]) {
  32. if (j != 0 && a1[i][j - 1])
  33. a1[i][j] += a1[i][j - 1];
  34. }
  35. }
  36. for (int i = 0; i < n; i++)
  37. for (int j = 0; j < n; j++) {
  38. if (a2[j][i]) {
  39. if (j != 0 && a2[j - 1][i])
  40. a2[j][i] += a2[j - 1][i];
  41. }
  42. }
  43. for (int i = 0; i < n; i++)
  44. for (int j = n - 1; j >= 0; j--) {
  45. if (a1[i][j] >= k) {
  46. for (int q = 1; q <= a1[i][j]; q++) {
  47. b[i][j - q + 1] = min(q, k);
  48. }
  49. for (int q = 1; q <= a1[i][j]; q++) {
  50. b[i][j - a1[i][j] + q] = min(b[i][j - a1[i][j] + q], min(q, a1[i][j] - k + 1));
  51. }
  52. j = j - a1[i][j] + 1;
  53.  
  54. }
  55. }
  56. for (int i = 0; i < n; i++)
  57. for (int j = n - 1; j >= 0; j--) {
  58. if (a2[j][i] >= k) {
  59. for (int q = 1; q <= a2[j][i]; q++) {
  60. c[j - q + 1][i] = min(q, k);
  61. }
  62. for (int q = 1; q <= a2[j][i]; q++) {
  63. c[j - a2[j][i] + q][i] = min(c[j - a2[j][i] + q][i], min(q, a2[j][i] - k + 1));
  64. }
  65. j = j - a2[j][i] + 1;
  66.  
  67. }
  68. }
  69. for (int i = 0; i < n; i++)
  70. for (int j = 0; j < n; j++) {
  71. b[i][j] += c[i][j];
  72. }
  73.  
  74. int x = 0, y = 0, kol = 0;
  75. /*for (int i = 0; i < n; i++) {
  76. for (int j = 0; j < n; j++) {
  77. cout << c[i][j];
  78. }
  79. cout << endl;
  80. }*/
  81. for (int i = 0; i < n; i++)
  82. for (int j = 0; j < n; j++) {
  83. if (b[i][j] > kol) {
  84. kol = b[i][j];
  85. x = i;
  86. y = j;
  87. }
  88. }
  89. x++;
  90. y++;
  91. cout << x << " " << y;
  92.  
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement