글 읽기 - 22%에서 틀렸다고 나옵니다.. 반례좀 찾아주세요..

utaein 4년 전 0

질문게시판의 반례들을 넣어보았음에도 어디서 틀렸는지 도저히 모르겠습니다...

#include <bits/stdc++.h>
using namespace std;

string str;
int n, m, a[1001][1001], ans, dp[1001][1001];
vector<pair<int,int>> v;

int recur(int x, int y){
    if(dp[x][y]) return dp[x][y];
    int cnt = 1;
    dp[x][y] = cnt;
    v.clear();
    while(true){
        bool no_rect = false;
        if(x+cnt > n or y+cnt > m ) break;
        for(int i=x; i<=x+cnt; i++){
            for(int j=y; j<=y+cnt; j++){
                if(a[i][j] == 0){
                    no_rect = true;
                    break;
                }
                if(i == x+cnt and j == y+cnt) continue;
                else{
                    v.push_back({i,j});
                }
            }
            if(no_rect) break;
        }
        if(no_rect) break;
        else{
            for(int i=0; i<v.size(); i++) dp[v[i].first][v[i].second] = cnt+1;
            v.clear();
        }
        cnt += 1;
    }
    return dp[x][y];
}
int main(void)
{
    //freopen("./INPUTS/1915.txt","rt",stdin);
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> str;
        for(int j=1; j<=m; j++)
            a[i][j] = (str[j-1]) - 48;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j]) ans = max(ans, recur(i,j));
        }
    }
    cout << ans*ans;
    return 0;
}

pichulia 4년 전 4

반례입니다.

게시판에 진짜 이런 예제가 없나요?

pichulia 4년 전 2

i==x+cnt and j==y+cnt는 갱신 안하는게 수상했었는데... 게시판에 있는 반례"만" 잘 나오게 짜셨던거네요 ㄷㄷ

utaein 4년 전 0

애초에 잘못된 방식으로 풀려고 했었다는 것을 깨달을 수 있었습니다. 소중한 시간 내주셔서 감사합니다.

kys4548 3년 전 0

오... 랭커님의 은총으로 해결할 수 있었습니다.

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

22%에서 틀렸다고 나옵니다.. 반례좀 찾아주세요..

utaein 4년 전 0

pichulia 4년 전 4

pichulia 4년 전 2

utaein 4년 전 0

kys4548 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말