結果
問題 | No.86 TVザッピング(2) |
ユーザー |
![]() |
提出日時 | 2020-11-05 09:42:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,580 bytes |
コンパイル時間 | 2,132 ms |
コンパイル使用メモリ | 173,408 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 12:54:45 |
合計ジャッジ時間 | 2,808 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;const int DY[] = {-1,0,1,0,-1,-1,1,1};const int DX[] = {0,1,0,-1,-1,1,-1,1};char A[110][110];int vis[110][110], N, M, cnt[110][110];bool f(){queue<pii> q;q.push(mp(0, 0));int ny, nx, y, x;while(sz(q)){tie(y, x) = q.front(); q.pop();if(vis[y][x]++)continue;rep(i, 8){ny = y + DY[i], nx = x + DX[i];if(ny >= 0 && nx >= 0 && ny < N&&nx < M){if(i < 4 && A[ny][nx] == '#' && !vis[ny][nx])q.push(mp(ny, nx));else if(A[ny][nx] == '.'){vis[ny][nx] = 1;cnt[ny][nx]++;}}}}int l = 0, r = 0;rep(i, N)rep(j, M)if(A[i][j]=='.'){if(!vis[i][j])return 0;if(cnt[i][j] == 1)r++;else if(cnt[i][j] >= 4)l++;}return (l == 4 && r == 0) || (l == 5 && r == 1);}int main(){MEM(A, '#');cin >> N >> M;rep(i, N){scanf("%s", A[i+1] + 1);A[i+1][M+1] = '#';}N += 2; M += 2;puts(f() ? "YES" : "NO");}