Hình vuông 0 1

Điểm: 0,11 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Ðược add lên bởi Võ Khánh Trung

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một bảng kích thước ~M \times N~, được chia thành lưới ô vuông đơn vị ~M~ dòng ~N~ cột ~(1 \le M~, ~N \le 1000)~

Trên các ô của bảng ghi số ~0~ hoặc ~1~. Các dòng của bảng được đánh số ~1~, ~2~ ...~M~ theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số ~1~, ~2~ ..., ~N~ theo thứ tự từ trái qua phải

Yêu cầu:

Hãy tìm một hình vuông gồm các ô của bảng thoả mãn các điều kiện sau:

Hình vuông là đồng nhất: tức là các ô thuộc hình vuông đó phải ghi các số giống nhau ~(0~ hoặc ~1)~
Cạnh hình vuông song song với cạnh bảng.
Kích thước hình vuông là lớn nhất có thể

Input

Dòng ~1~: Ghi hai số ~M~, ~N~

~M~ dòng tiếp theo, dòng thứ ~i~ ghi ~N~ số mà số thứ ~j~ là số ghi trên ô ~(i~, ~j)~ của bảng

Output

Gồm 1 dòng duy nhất ghi kích thước cạnh của hình vuông tìm được

Sample Input

11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

vominhmanh10 đã bình luận lúc 24, Tháng 11, 2025, 2:29

bài này với py lại là vấn đề input, ta đọc toàn bộ trước

import sys
input = sys.stdin.readline


def solve():
    data = sys.stdin.read().split()
    m, n = map(int, data[0:2])
    a = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            a[i][j] = int(data[2 + n * i + j])
    pre = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + a[i - 1][j - 1]

    lo, hi = 0, min(m, n)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        f = False
        for i in range(mid, m + 1):
            for j in range(mid, n + 1):
                s = pre[i][j] - pre[i - mid][j] - pre[i][j - mid] + pre[i - mid][j - mid]
                if s == 0 or s == mid * mid: f = True
            if f: break
        if f: lo = mid
        else: hi = mid - 1
    print(lo)
solve()

-1

lenamphong03122012 đã bình luận lúc 31, Tháng 10, 2025, 12:40 ← chỉnh sửa →

Mình thấy bài này tìm kiếm nhị phân thuần tuý cũng được mà nhỉ

Code cho ai cần:

// code by phongln
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define fo(i, a, b, k) for(ll i=a; i<=b; i+=k)
#define fod(i, a, b, k) for(ll i=a; i>=b; i-=k)
#define lop(x, s) for(auto x : s)
#define sz(s) s.size()
#define all(s) s.begin(), s.end()
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define sq(a) (a)*(a)
#define cb(a) (a)*(a)*(a)
#define NAME "TEST"
const ll inf=1e18;
const ll mod=1e9+7;
const ll maxn=1e3+5;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

ll m, n, a[maxn][maxn], p[maxn][maxn];

bool ck(ll x){
    fo(i, x, m, 1){
        fo(j, x, n, 1){
            ll sum=p[i][j]-p[i-x][j]-p[i][j-x]+p[i-x][j-x];
            if(sum==x*x or sum==0){
                return 1;
            }
        }
    }
    return 0;
}

void init(){
}

void solve(){
    cin >> m >> n;
    fo(i, 1, m, 1){
        fo(j, 1, n, 1){
            cin >> a[i][j];
            p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+a[i][j];
        }
    }
    ll l=1, r=min(m, n), ans;
    while(l<=r){
        ll mid=(l+r)/2;
        if(ck(mid)){
            ans=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(NAME".INP", "r", stdin);
    // freopen(NAME".OUT", "w", stdout);
    init();
    ll t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Xin lỗi vì code không sạch ;))

-5

hailomathepuck đã bình luận lúc 13, Tháng 5, 2025, 14:40

arg k có 1 đấmmmmm roii

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

pppssslc đã bình luận lúc 18, Tháng 4, 2025, 15:38 ← sửa 14 →

Spoil!!!

Vì ko thấy ai dùng binary search nên mình xin chia sẻ.

Tạo 1 prefix sum 2 chiều để thuận tiện cho việc kiểm tra các ô vuông.

Dùng binary search kiểm tra các độ dài cạnh, nếu có hình vuông có độ dài cạnh tương ứng thỏa mãn điều kiện đề bài thì tăng lên và ngược lại.

Tại mỗi độ dài cạnh đang kiểm tra, kiểm tra từng ô vuông, sử dụng prefix sum vừa tạo để tối ưu cho việc kiểm tra.

Độ phức tạp: ~O(n^2\log_2(n))~.

Code:

#include<bits/stdc++.h>
#define str string
#define ll long long
#define db double
#define pii pair < int, int>
#define piii pair < int, pii>
#define piiii pair < pii, pii>
#define se second
#define fi first
#define vi vector<int>
#define vii vector<vector<int>>
#define mpii map < int, int>
#define umpii unordered_map < int, int>
#define si set<int>
#define usa unordered_set<int>
#define mulsi multiset<int>
using namespace std;

const int mod=1e9+7;
const int maxn=1e3+1;

int f[maxn][maxn], a[maxn][maxn];
int n, m;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j)cin>>a[i][j];
    }
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j)f[i][j]=f[i][j-1]+a[i][j];
    }
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j)f[i][j]=f[i-1][j]+f[i][j];
    }
    int l=1, r=min(m, n), res=1;
    while(l<=r){
        int mid=l+r>>1;
        bool check=false;
        for(int i=1; i<=n-mid+1; ++i){
            for(int j=1; j<=m-mid+1; ++j){
                int sum_sqr=f[i+mid-1][j+mid-1]+f[i-1][j-1]-f[i-1][j+mid-1]-f[i+mid-1][j-1];
                if(sum_sqr==0 || sum_sqr==mid*mid){
                    check=true;
                    break;
                }
            }
        }
        if(check){l=mid+1; res=mid;
        }else r=mid-1;
    }
    cout << res;
    return 0;
}

Lần đầu viết sol có gì sai sót mong mọi người góp ý.😁

-4

nguyenthingoc22031969 đã bình luận lúc 13, Tháng 3, 2025, 12:33

test cuối bài này bị j thế

-52

danglebinhnguyen2014 đã bình luận lúc 9, Tháng 12, 2024, 5:35

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-19

Cuunon311 đã bình luận lúc 9, Tháng 10, 2023, 12:47

bai nay hay

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

92

HV_DuongPhucThienNhan_BL_2022 đã bình luận lúc 28, Tháng 1, 2022, 15:55 ← sửa 2 →

Lời giải ở đây:

https://vietcodes.github.io/code/161/index.html

Please don't downvote me:(