Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <climits>
- using namespace std;
- pair<int, int> findLargestSquareWithKFlips(const vector<vector<int>>& matrix, int k) {
- if(matrix.empty() || matrix[0].empty())
- return {-1, -1};
- int n = matrix.size(), m = matrix[0].size();
- // Build a prefix sum matrix for counting zeros.
- // prefix[i+1][j+1] = number of zeros in submatrix from (0,0) to (i,j)
- vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- int isZero = (matrix[i][j] == 0) ? 1 : 0;
- prefix[i+1][j+1] = isZero + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j];
- }
- }
- // Function to count zeros in a submatrix with top-left (i,j) and side length L.
- auto countZeros = [&](int i, int j, int L) -> int {
- return prefix[i + L][j + L] - prefix[i][j + L] - prefix[i + L][j] + prefix[i][j];
- };
- // Binary search for the maximum square side length that can be achieved.
- int low = 1, high = min(n, m), best = 0;
- pair<int, int> bestPos = {-1, -1};
- while(low <= high) {
- int mid = (low + high) / 2;
- bool found = false;
- pair<int, int> curPos = {-1, -1};
- for (int i = 0; i <= n - mid; i++){
- for (int j = 0; j <= m - mid; j++){
- int zeros = countZeros(i, j, mid);
- if(zeros <= k) {
- found = true;
- curPos = {i, j};
- break;
- }
- }
- if(found) break;
- }
- if(found) {
- best = mid;
- bestPos = curPos;
- low = mid + 1; // try to find a larger square
- } else {
- high = mid - 1;
- }
- }
- return bestPos;
- }
- int main() {
- // Example input:
- // First line: n m k
- // Next n lines: each containing m binary digits (0 or 1)
- // For instance:
- // 5 5 2
- // 1 1 1 1 1
- // 1 0 0 1 1
- // 1 1 1 1 1
- // 1 1 0 1 1
- // 1 1 1 1 1
- int n, m, k;
- cin >> n >> m >> k;
- vector<vector<int>> matrix(n, vector<int>(m));
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- cin >> matrix[i][j];
- }
- }
- pair<int, int> ans = findLargestSquareWithKFlips(matrix, k);
- cout << "Upper-left corner of largest square: " << ans.first << " " << ans.second << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment