結果
問題 | No.2641 draw X |
ユーザー |
|
提出日時 | 2024-02-19 22:22:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 3,356 bytes |
コンパイル時間 | 2,330 ms |
コンパイル使用メモリ | 208,180 KB |
最終ジャッジ日時 | 2025-02-19 17:10:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define REP(i, n) for(ll i = 0;i < n;i++)#define REPR(i, n) for(ll i = n;i >= 0;i--)#define FOR(i, m, n) for(ll i = m;i < n;i++)#define FORR(i, m, n) for(ll i = m;i >= n;i--)#define REPO(i, n) for(ll i = 1;i <= n;i++)#define ll long long#define INF (ll)1ll << 60#define MINF (-1 * INF)#define ALL(n) n.begin(),n.end()#define MOD (ll)1000000007#define P pair<ll, ll>ll h, w;vector<string> s;vector<vector<ll>> v[4], r[4];bool check(ll x, ll y){if(0 <= x and x < h and 0 <= y and y < w) return true;return false;}void solve(ll num, ll x0, ll y0, ll dx1, ll dy1, ll dx2, ll dy2, ll dx, ll dy){ll x = x0, y = y0;while(1){ll nx = x, ny = y, now = 0;while(1){if(s[nx][ny] == '#'){now++;}else now = 0;v[num][nx][ny] = now;if(!check(nx + dx, ny + dy))break;nx += dx;ny += dy;}if(!check(x + dx1, y + dy1))break;x += dx1;y += dy1;}x += dx2;y += dy2;if(!check(x + dx2, y + dy2))return;while(1){ll nx = x, ny = y, now = 0;while(1){if(s[nx][ny] == '#'){now++;}else now = 0;v[num][nx][ny] = now;if(!check(nx + dx, ny + dy))break;nx += dx;ny += dy;}if(!check(x + dx2, y + dy2))break;x += dx2;y += dy2;}}void solve2(ll num, ll x0, ll y0, ll dx1, ll dy1, ll dx2, ll dy2, ll dx, ll dy){ll x = x0, y = y0;while(1){ll nx = x, ny = y, now = 0;while(1){now = max(now - 1, r[num][nx][ny]);r[num][nx][ny] = now;if(!check(nx + dx, ny + dy))break;nx += dx;ny += dy;}if(!check(x + dx1, y + dy1))break;x += dx1;y += dy1;}x += dx2;y += dy2;if(!check(x + dx2, y + dy2))return;while(1){ll nx = x, ny = y, now = 0;while(1){now = max(now - 1, r[num][nx][ny]);r[num][nx][ny] = now;if(!check(nx + dx, ny + dy))break;nx += dx;ny += dy;}if(!check(x + dx2, y + dy2))break;x += dx2;y += dy2;}}int main(){cin >> h >> w;s.resize(h);REP(i, 4) v[i].resize(h, vector<ll>(w));REP(i, 4) r[i].resize(h, vector<ll>(w));REP(i, h)cin >> s[i];solve(0, 0, w - 1, 0, -1, 1, 0, 1, 1);solve(1, 0, 0, 0, 1, 1, 0, 1, -1);solve(2, h - 1, 0, 0, 1, -1, 0, -1, -1);solve(3, 0, 0, 1, 0, 0, 1, -1, 1);REP(i, h){REP(j, w){ll now = INF;REP(k, 4)now = min(now, v[k][i][j]);if(now >= 2){REP(k, 4) r[k][i][j] = now;}}}solve2(0, 0, w - 1, 0, -1, 1, 0, 1, 1);solve2(1, 0, 0, 0, 1, 1, 0, 1, -1);solve2(2, h - 1, 0, 0, 1, -1, 0, -1, -1);solve2(3, 0, 0, 1, 0, 0, 1, -1, 1);REP(i, h){REP(j, w){ll now = 0;REP(k, 4)now = max(now, r[k][i][j]);if(now == 0 and s[i][j] == '#'){cout <<"No" << endl;return 0;}}}cout <<"Yes"<<endl;}