結果

問題 No.86 TVザッピング(2)
コンテスト
ユーザー pessimist
提出日時 2025-06-19 00:52:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,542 bytes
コンパイル時間 2,017 ms
コンパイル使用メモリ 196,328 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 14:03:02
合計ジャッジ時間 3,080 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

string S[101];
int total;
int sumH[101][101];
int sumV[101][101];
int getSumH(int x, int l, int r){
    if(sumH[x][r+1]-sumH[x][l]==r-l+1) return r-l+1;
    return -100000;
}
int getSumV(int y, int t, int b){
    if(sumV[b+1][y]-sumV[t][y]==b-t+1) return b+1-t;
    return -100000;
}
int N,M;
int lef=10000, rght=0;
int top=100000,bottom=0;
void solve(){
    cin>>N>>M;
    for(int x=0;x<N;++x) cin>>S[x];

    for(int x=0;x<N;++x){
        for(int y=0;y<M;++y){
            if(S[x][y]=='.'){
                ++total;
                lef=min(lef,y);
                rght=max(rght,y);
                top=min(top,x);
                bottom=max(bottom,x);
            }
        }
    }
    if(rght-lef<1 || bottom-top<1){
        cout<<"NO"<<endl;
        return;
    }

    for(int x=0;x<N;++x){
        for(int y=0;y<M;++y){
            sumH[x][y+1]=sumH[x][y]+(S[x][y]=='.');
        }
    }

    for(int x=0;x<N;++x){
        for(int y=0;y<M;++y){
            sumV[x+1][y]=sumV[x][y]+(S[x][y]=='.');
        }
    }
    
    auto OK=[&](){ cout<<"YES"<<endl; };
    
    int sum=0;
    sum+=getSumH(top,lef,rght)+getSumH(bottom,lef,rght);
    sum+=getSumV(lef,top,bottom)+getSumV(rght,top,bottom);
    sum-=4;
    if(sum==total) return OK();

    for(int x=top+1;x<bottom;++x){
        for(int y=lef+1;y<rght;++y){
            if(S[x][y]=='.'){
                sum=getSumH(top,lef,y)+getSumH(x,y,rght)+getSumH(bottom,lef,rght);
                sum+=getSumV(lef,top,bottom)+getSumV(y,top,x)+getSumV(rght,x,bottom);
                sum-=6;
                if(sum==total) return OK();

                sum=getSumH(x,lef,y)+getSumH(top,y,rght)+getSumH(bottom,lef,rght);
                sum+=getSumV(lef,x,bottom)+getSumV(y,top,x)+getSumV(rght,top,bottom);
                sum-=6;
                if(sum==total) return OK();

                sum=getSumH(top,lef,rght)+getSumH(x,y,rght)+getSumH(bottom,lef,y);
                sum+=getSumV(lef,top,bottom)+getSumV(y,x,bottom)+getSumV(rght,top,y);
                sum-=6;
                if(sum==total) return OK();
                
                sum=getSumH(top,lef,rght)+getSumH(x,lef,y)+getSumH(bottom,y,rght);
                sum+=getSumV(lef,top,x)+getSumV(y,x,bottom)+getSumV(rght,top,bottom);
                sum-=6;
                if(sum==total) return OK();
            }
        }
    }
    cout<<"NO"<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1; //cin>>t;
    for(;t--;) solve();
}
0