結果
問題 | No.2641 draw X |
ユーザー |
|
提出日時 | 2024-02-20 10:17:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 2,034 bytes |
コンパイル時間 | 796 ms |
コンパイル使用メモリ | 83,968 KB |
最終ジャッジ日時 | 2025-02-19 17:57:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H,W; cin>>H>>W; vector<string>S(H); for(int i=0;i<H;i++)cin>>S[i]; vector V(4,vector(H,vector<int>(W))); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(S[i][j]=='#'){ V[0][i][j]=(i-1>=0&&j-1>=0?V[0][i-1][j-1]:0)+1; V[1][i][j]=(i-1>=0&&j+1<W?V[1][i-1][j+1]:0)+1; } } } for(int i=H-1;i>=0;i--){ for(int j=0;j<W;j++){ if(S[i][j]=='#'){ V[2][i][j]=(i+1<H&&j+1<W?V[2][i+1][j+1]:0)+1; V[3][i][j]=(i+1<H&&j-1>=0?V[3][i+1][j-1]:0)+1; } } } vector X(H+1,vector<int>(W+1)),Y(H+1,vector<int>(W+1)); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(S[i][j]=='#'){ int l=1<<30; for(int k=0;k<4;k++){ chmin(l,V[k][i][j]); } l--; if(l>0){ X[i-l][j-l]++; X[i+l+1][j+l+1]--; Y[i-l][j+l+1]++; Y[i+l+1][j-l]--; } } } } for(int i=1;i<=H;i++){ for(int j=1;j<=W;j++){ X[i][j]+=X[i-1][j-1]; } } for(int i=1;i<=H;i++){ for(int j=0;j<W;j++){ Y[i][j]+=Y[i-1][j+1]; } } for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ int sum=X[i][j]+Y[i][j+1]; if((sum>0&&S[i][j]=='.')||(sum==0&&S[i][j]=='#')){ cout<<"No"<<"\n"; return 0; } } } cout<<"Yes"<<"\n"; }