#1160533 (C++17(gnu拡張)) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: ,
• 提出日時: 2026-04-19 16:06:23
• 言語: C++17(gnu拡張) (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,116 bytes
• コンパイル時間: 489 ms
• コンパイル使用メモリ: 45,952 KB
• 実行使用メモリ: 66,560 KB
• 最終ジャッジ日時: 2026-04-19 16:06:36
• 合計ジャッジ時間: 12,665 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 56 WA * 29

ソースコード

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXN 2001
#define MAXHW (MAXN*MAXN)

int H, W;
char grid[MAXN][MAXN+1];
int dist[MAXHW];
char vis[MAXHW];
char inq[MAXHW];
int queue[MAXHW];
int pend[MAXN][MAXN];  // pend[row] = list of positions
int pend_cnt[MAXN];

static inline int pos(int i, int j) { return i*W+j; }

int bfs0() {
    memset(dist, -1, sizeof(int)*H*W);
    if (grid[0][0] == '#') return -1;
    dist[0] = 0;
    int head=0, tail=0;
    queue[tail++] = 0;
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while (head < tail) {
        int p = queue[head++];
        int i=p/W, j=p%W, d=dist[p]+1;
        for (int k=0;k<4;k++) {
            int ni=i+dirs[k][0], nj=j+dirs[k][1];
            if (ni>=0&&ni<H&&nj>=0&&nj<W) {
                int np=ni*W+nj;
                if (dist[np]==-1 && grid[ni][nj]!='#') {
                    dist[np]=d;
                    queue[tail++]=np;
                }
            }
        }
    }
    return dist[H*W-1];
}

// Restricted BFS: row-forward (vis_top)
void rbfs_row(int start, int forward, char* vis_out) {
    memset(vis_out, 0, H*W);
    memset(inq, 0, H*W);
    for (int i=0;i<H;i++) pend_cnt[i]=0;
    if (grid[start/W][start%W]=='#') return;
    inq[start]=1;
    pend[start/W][pend_cnt[start/W]++] = start;
    
    // Use a separate queue for BFS within each row
    static int q2[MAXHW];
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    
    for (int row = (forward?0:H-1); forward?(row<H):(row>=0); row+=(forward?1:-1)) {
        int nrow = forward ? row+1 : row-1;
        int head=0, tail=0;
        for (int k=0;k<pend_cnt[row];k++) {
            q2[tail++] = pend[row][k];
        }
        while (head < tail) {
            int p = q2[head++];
            if (vis_out[p]) continue;
            vis_out[p] = 1;
            int i=p/W, j=p%W;
            for (int k=0;k<4;k++) {
                int ni=i+dirs[k][0], nj=j+dirs[k][1];
                if (ni>=0&&ni<H&&nj>=0&&nj<W) {
                    int np=ni*W+nj;
                    if (!inq[np] && grid[ni][nj]!='#') {
                        inq[np]=1;
                        if (forward) {
                            if (ni<=row) q2[tail++]=np;
                            else if (ni==nrow && nrow<H) pend[nrow][pend_cnt[nrow]++]=np;
                        } else {
                            if (ni>=row) q2[tail++]=np;
                            else if (ni==nrow && nrow>=0) pend[nrow][pend_cnt[nrow]++]=np;
                        }
                    }
                }
            }
        }
    }
}

void rbfs_col(int start, int forward, char* vis_out) {
    memset(vis_out, 0, H*W);
    memset(inq, 0, H*W);
    for (int i=0;i<W;i++) pend_cnt[i]=0;
    if (grid[start/W][start%W]=='#') return;
    inq[start]=1;
    pend[start%W][pend_cnt[start%W]++] = start;
    
    static int q2[MAXHW];
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    
    for (int col = (forward?0:W-1); forward?(col<W):(col>=0); col+=(forward?1:-1)) {
        int ncol = forward ? col+1 : col-1;
        int head=0, tail=0;
        for (int k=0;k<pend_cnt[col];k++) {
            q2[tail++] = pend[col][k];
        }
        while (head < tail) {
            int p = q2[head++];
            if (vis_out[p]) continue;
            vis_out[p] = 1;
            int i=p/W, j=p%W;
            for (int k=0;k<4;k++) {
                int ni=i+dirs[k][0], nj=j+dirs[k][1];
                if (ni>=0&&ni<H&&nj>=0&&nj<W) {
                    int np=ni*W+nj;
                    if (!inq[np] && grid[ni][nj]!='#') {
                        inq[np]=1;
                        if (forward) {
                            if (nj<=col) q2[tail++]=np;
                            else if (nj==ncol && ncol<W) pend[ncol][pend_cnt[ncol]++]=np;
                        } else {
                            if (nj>=col) q2[tail++]=np;
                            else if (nj==ncol && ncol>=0) pend[ncol][pend_cnt[ncol]++]=np;
                        }
                    }
                }
            }
        }
    }
}

static char vt[MAXHW], vb[MAXHW], vl[MAXHW], vr[MAXHW];

int main() {
    scanf("%d %d", &H, &W);
    for (int i=0;i<H;i++) scanf("%s", grid[i]);
    
    int d0 = bfs0();
    int best = (d0==-1) ? H+W+10 : d0;
    
    rbfs_row(0, 1, vt);
    rbfs_row(H*W-1, 0, vb);
    
    int one_ins = 0;
    for (int g=0; g<H-1 && !one_ins; g++) {
        int top_ok=0, bot_ok=0;
        for (int j=0;j<W;j++) { if(vt[g*W+j]) {top_ok=1; break;} }
        for (int j=0;j<W;j++) { if(vb[(g+1)*W+j]) {bot_ok=1; break;} }
        if (top_ok && bot_ok) one_ins=1;
    }
    
    if (!one_ins) {
        rbfs_col(0, 1, vl);
        rbfs_col(H*W-1, 0, vr);
        for (int g=0; g<W-1 && !one_ins; g++) {
            int l_ok=0, r_ok=0;
            for (int i=0;i<H;i++) { if(vl[i*W+g]) {l_ok=1; break;} }
            for (int i=0;i<H;i++) { if(vr[i*W+g+1]) {r_ok=1; break;} }
            if (l_ok && r_ok) one_ins=1;
        }
    }
    
    if (one_ins) best = best < H+W-1 ? best : H+W-1;
    best = best < H+W ? best : H+W;
    printf("%d\n", best);
    return 0;
}