Hình vuông 0 1

View as PDF

Submit solution

All submissions

Read editorial

Points: 0.04 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

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

Problem types

Allowed languages

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

Comments

Comments

Please read the guidelines before commenting.

vominhmanh10 commented on Nov. 24, 2025, 2:29 a.m.

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()

-2

lenamphong03122012 commented on Oct. 31, 2025, 12:40 p.m. ← edited →

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 commented on May 13, 2025, 2:40 p.m.

arg k có 1 đấmmmmm roii

This comment is hidden due to too much negative feedback. Show it anyway.

pppssslc commented on April 18, 2025, 3:38 p.m. ← edit 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 commented on March 13, 2025, 12:33 p.m.

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

-53

danglebinhnguyen2014 commented on Dec. 9, 2024, 5:35 a.m.

This comment is hidden due to too much negative feedback. Show it anyway.

-19

Cuunon311 commented on Oct. 9, 2023, 12:47 p.m.

bai nay hay

This comment is hidden due to too much negative feedback. Show it anyway.

92

HV_DuongPhucThienNhan_BL_2022 commented on Jan. 28, 2022, 3:55 p.m. ← edit 2 →

Lời giải ở đây:

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

Please don't downvote me:(