結果
| 問題 | No.3813 Ashwreath |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-21 04:17:02 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 7,378 bytes |
| 記録 | |
| コンパイル時間 | 1,770 ms |
| コンパイル使用メモリ | 232,112 KB |
| 実行使用メモリ | 39,388 KB |
| 最終ジャッジ日時 | 2026-11-21 04:17:45 |
| 合計ジャッジ時間 | 9,868 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 WA * 3 |
ソースコード
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,M; cin >> N >> M;
if(min(N,M) == 1){cout << "0\n"; return 0;}
vector<string> S(N);
for(auto &s : S) cin >> s;
auto chmax = [&](int &a,int b) -> void {a=max(a,b);};
int K = 1<<(M*2+2),mask = K-1;
vector<bool> P1(K),P2(K),P3(K);
vector<bool> B1(K),B2(K),B3(K);
for(int i=0; i<K; i++){
{
int to = i*2+1;
if((to>>(M+1))&1) P1.at(i) = true;
else{
int plant = 0;
if((to>>(2*M+1))&1) plant++;
if((to>>(2*M))&1) plant++;
if((to>>M)&1) plant++;
if((to>>1)&1) plant++;
if((to>>0)&1) plant++;
if(plant >= 2) P1.at(i) = true;
}
}
{
int to = i*2;
if((to>>(M+1))&1) B1.at(i) = true;
else{
int plant = 0;
if((to>>(2*M+1))&1) plant++;
if((to>>(2*M))&1) plant++;
if((to>>M)&1) plant++;
if((to>>1)&1) plant++;
if((to>>0)&1) plant++;
if(plant >= 2) B1.at(i) = true;
}
}
{
int to = i*2+1;
if((to>>(M+1))&1) P2.at(i) = true;
else{
int plant = 0;
if((to>>(2*M+2))&1) plant++;
if((to>>(2*M+1))&1) plant++;
if((to>>(2*M))&1) plant++;
if((to>>(M+2))&1) plant++;
if((to>>M)&1) plant++;
if((to>>2)&1) plant++;
if((to>>1)&1) plant++;
if((to>>0)&1) plant++;
if(plant >= 2) P2.at(i) = true;
}
}
{
int to = i*2;
if((to>>(M+1))&1) B2.at(i) = true;
else{
int plant = 0;
if((to>>(2*M+2))&1) plant++;
if((to>>(2*M+1))&1) plant++;
if((to>>(2*M))&1) plant++;
if((to>>(M+2))&1) plant++;
if((to>>M)&1) plant++;
if((to>>2)&1) plant++;
if((to>>1)&1) plant++;
if((to>>0)&1) plant++;
if(plant >= 2) B2.at(i) = true;
}
}
{
int to = i*2+1;
if((to>>(M+1))&1) P3.at(i) = true;
else{
int plant = 0;
if((to>>(2*M+2))&1) plant++;
if((to>>(2*M+1))&1) plant++;
if((to>>(M+2))&1) plant++;
if((to>>2)&1) plant++;
if((to>>1)&1) plant++;
if(plant >= 2) P3.at(i) = true;
}
}
{
int to = i*2;
if((to>>(M+1))&1) B3.at(i) = true;
else{
int plant = 0;
if((to>>(2*M+2))&1) plant++;
if((to>>(2*M+1))&1) plant++;
if((to>>(M+2))&1) plant++;
if((to>>2)&1) plant++;
if((to>>1)&1) plant++;
if(plant >= 2) B3.at(i) = true;
}
}
}
vector<int> dp(K,-1);
dp.at(0) = 0;
for(int x=0; x<N; x++) for(int y=0; y<M; y++){
char check = '-';
if(x > 1 || (x == 1 && y >= 1)){
if(y == 0) check = S.at(x-2).at(M-1);
else check = S.at(x-1).at(y-1);
}
vector<int> next(K,-1);
if(S.at(x).at(y) == '.'){
int fire = 0;
for(int dx=-1; dx<=1; dx++) for(int dy=-1; dy<=1; dy++){
int nx = x+dx,ny = y+dy;
if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if(S.at(nx).at(ny) == '#') fire++;
}
if(check == '.'){
if(fire >= 2){
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
if(y == 0){
if(B3.at(i)) chmax(next.at((i*2)&mask),v+1);
}
else if(y == 1){
if(B1.at(i)) chmax(next.at((i*2)&mask),v+1);
}
else if(B2.at(i)) chmax(next.at((i*2)&mask),v+1);
}
}
{
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
if(y == 0){
if(P3.at(i)) chmax(next.at((i*2+1)&mask),v);
}
else if(y == 1){
if(P1.at(i)) chmax(next.at((i*2+1)&mask),v);
}
else if(P2.at(i)) chmax(next.at((i*2+1)&mask),v);
}
}
}
else{
if(fire >= 2){
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
chmax(next.at((i*2)&mask),v+1);
}
}
{
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
chmax(next.at((i*2+1)&mask),v);
}
}
}
}
else{
if(check == '.'){
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
if(y == 0){
if(B3.at(i)) chmax(next.at((i*2)&mask),v);
}
else if(y == 1){
if(B1.at(i)) chmax(next.at((i*2)&mask),v);
}
else if(B2.at(i)) chmax(next.at((i*2)&mask),v);
}
}
else{
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
chmax(next.at((i*2)&mask),v);
}
}
}
swap(dp,next);
}
int answer = 0;
for(int i=0; i<K; i++){
int v = dp.at(i);
if(v == -1) continue;
bool ok = true;
if(B3.at(i)){
for(int y=0; y<M; y++) if(S.at(N-1).at(y) == '.'){
int d = M-1-y;
if((i>>d)&1) continue;
int plant = 0;
if(y == 0){
if((i>>(d+M))&1) plant++;
if((i>>(d+M-1))&1) plant++;
if((i>>(d-1))&1) plant++;
}
else if(y == M-1){
if((i>>(d+M+1))&1) plant++;
if((i>>(d+M))&1) plant++;
if((i>>(d+1))&1) plant++;
}
else{
if((i>>(d+M+1))&1) plant++;
if((i>>(d+M))&1) plant++;
if((i>>(d+M-1))&1) plant++;
if((i>>(d+1))&1) plant++;
if((i>>(d-1))&1) plant++;
}
if(plant < 2){ok = false; break;}
}
if(ok) answer = max(answer,v);
}
}
cout << answer << endl;
}