aqibm

Untitled

Apr 6th, 2025
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. pair<int, int> findLargestSquareWithKFlips(const vector<vector<int>>& matrix, int k) {
  8. if(matrix.empty() || matrix[0].empty())
  9. return {-1, -1};
  10.  
  11. int n = matrix.size(), m = matrix[0].size();
  12.  
  13. // Build a prefix sum matrix for counting zeros.
  14. // prefix[i+1][j+1] = number of zeros in submatrix from (0,0) to (i,j)
  15. vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));
  16. for (int i = 0; i < n; i++){
  17. for (int j = 0; j < m; j++){
  18. int isZero = (matrix[i][j] == 0) ? 1 : 0;
  19. prefix[i+1][j+1] = isZero + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j];
  20. }
  21. }
  22.  
  23. // Function to count zeros in a submatrix with top-left (i,j) and side length L.
  24. auto countZeros = [&](int i, int j, int L) -> int {
  25. return prefix[i + L][j + L] - prefix[i][j + L] - prefix[i + L][j] + prefix[i][j];
  26. };
  27.  
  28. // Binary search for the maximum square side length that can be achieved.
  29. int low = 1, high = min(n, m), best = 0;
  30. pair<int, int> bestPos = {-1, -1};
  31.  
  32. while(low <= high) {
  33. int mid = (low + high) / 2;
  34. bool found = false;
  35. pair<int, int> curPos = {-1, -1};
  36.  
  37. for (int i = 0; i <= n - mid; i++){
  38. for (int j = 0; j <= m - mid; j++){
  39. int zeros = countZeros(i, j, mid);
  40. if(zeros <= k) {
  41. found = true;
  42. curPos = {i, j};
  43. break;
  44. }
  45. }
  46. if(found) break;
  47. }
  48.  
  49. if(found) {
  50. best = mid;
  51. bestPos = curPos;
  52. low = mid + 1; // try to find a larger square
  53. } else {
  54. high = mid - 1;
  55. }
  56. }
  57.  
  58. return bestPos;
  59. }
  60.  
  61. int main() {
  62. // Example input:
  63. // First line: n m k
  64. // Next n lines: each containing m binary digits (0 or 1)
  65. // For instance:
  66. // 5 5 2
  67. // 1 1 1 1 1
  68. // 1 0 0 1 1
  69. // 1 1 1 1 1
  70. // 1 1 0 1 1
  71. // 1 1 1 1 1
  72. int n, m, k;
  73. cin >> n >> m >> k;
  74. vector<vector<int>> matrix(n, vector<int>(m));
  75. for (int i = 0; i < n; i++){
  76. for (int j = 0; j < m; j++){
  77. cin >> matrix[i][j];
  78. }
  79. }
  80.  
  81. pair<int, int> ans = findLargestSquareWithKFlips(matrix, k);
  82. cout << "Upper-left corner of largest square: " << ans.first << " " << ans.second << endl;
  83.  
  84. return 0;
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment