TPC追いコン A - 不完全迷路 ( BFS )

A: 不完全迷路 - TPC追いコン | AtCoder
Short summary for statement: Given a graph where '.' indicates path and '#' indicates wall which shall not be penetrated, find the maximum distance from 'S' to 'G', where any but only one '#' can be changed to '.'. It is guaranteed that in the initial graph, 'S' and 'G' are not connected.
Solution: If we simply enumerate each '#' that transforms to '.', and perform BFS each new enumeration, the overall complexity will be O( N ^ 4 ) which will get us TLE since N ≤ 300. However, we will find that most of the paths we have searched through for shortest distance are duplicated and will be wasted if we do a complete new search again each time. Realizing that once some '#' has been chosen to be transformed to '.', if now 'S' and 'G' are connected, the new shortest path must be
distance from '.' adjacent with this to 'S' + distance from another '.' adjacent with this to 'G' + 2
thus we will only have to precompute distance from each cell to the start and the goal.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXH = 300;
const int MAXW = 300;
const int INF = 1e9;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int h, w;
char G[ MAXH ][ MAXW ];
int sx, sy, gx, gy;
int dis[ 2 ][ MAXH ][ MAXW ];

void bfs(int k, int sx, int sy){
    queue< pii > que;
    que.push( pii( sx, sy ) );
    dis[ k ][ sx ][ sy ] = 0;
    while( !que.empty() ){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for(int d = 0; d < 4; ++d){
            int nx = x + dx[ d ];
            int ny = y + dy[ d ];
            if( nx < 1 || nx > h || ny < 1 || ny > w ) continue;
            if( G[ nx ][ ny ] == '#' ) continue;
            if( dis[ k ][ nx ][ ny ] <= dis[ k ][ x ][ y ] + 1 ) continue;
            dis[ k ][ nx ][ ny ] = dis[ k ][ x ][ y ] + 1;
            que.push( pii( nx, ny ) );
        }
    }
}

void init(){
    scanf("%d%d", &h, &w);
    for(int i = 1; i <= h; ++i)
        scanf("%s", &G[ i ][ 1 ]);
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j){
            dis[ 0 ][ i ][ j ] = dis[ 1 ][ i ][ j ] = INF;
            if( G[ i ][ j ] == 'S' ) sx = i, sy = j;
            if( G[ i ][ j ] == 'G' ) gx = i, gy = j;
        }
    bfs( 0, sx, sy );
    bfs( 1, gx, gy );
}

void solve(){
    int ans = 0;
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j) if( G[ i ][ j ] == '#' ){
            int d = INF;
            for(int k = 0; k < 4; ++k)
                for(int l = 0; l < 4; ++l) if( k != l ){
                    int nx1 = i + dx[ k ], ny1 = j + dy[ k ];
                    int nx2 = i + dx[ l ], ny2 = j + dy[ l ];
                    if( nx1 < 1 || nx1 > h || ny1 < 1 || ny1 > w ) continue;
                    if( nx2 < 1 || nx2 > h || ny2 < 1 || ny2 > w ) continue;
                    d = min<int>( d, dis[ 0 ][ nx1 ][ ny1 ] + dis[ 1 ][ nx2 ][ ny2 ] + 2 );
                }
            if( d < INF ) ans = max<int>( ans, d );
        }
    printf("%d\n", ans);
}

int main(){
    init();
    solve();
    return 0;
}

A TLE solution.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXH = 300;
const int MAXW = 300;
const int INF = 1e9;
 
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
 
int h, w;
char G[ MAXH ][ MAXW ];
int sx, sy, gx, gy;
 
int vis[ MAXH ][ MAXW ];
int bfs(int bx, int by){ // ( bx, by ) '#' -> '.'
    G[ bx ][ by ] = '.';
    queue< pii > que;
    que.push( pii( 0, sx * MAXW + sy ) );
    memset( vis, 0, sizeof(vis) );
    vis[ sx ][ sy ] = 1;
    int res = INF;
    while( !que.empty() ){
        int t = que.front().first;
        int x = que.front().second / MAXW;
        int y = que.front().second % MAXW;
        que.pop();
        if( x == gx && y == gy ){
            res = t;
            break;
        }
        for(int d = 0; d < 4; ++d){
            int nx = x + dx[ d ];
            int ny = y + dy[ d ];
            if( nx < 1 || ny < 1 || nx > h || ny > w ) continue;
            if( G[ nx ][ ny ] == '#' ) continue;
            if( vis[ nx ][ ny ] ) continue;
            vis[ nx ][ ny ] = 1;
            que.push( pii( t + 1, nx * MAXW + ny ) );
        }
    }
    G[ bx ][ by ] = '#';
    return res;
}
 
void solve(){
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j){
            if( G[ i ][ j ] == 'S' ) sx = i, sy = j;
            if( G[ i ][ j ] == 'G' ) gx = i, gy = j;
        }
    int ans = 0;
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j) if( G[ i ][ j ] == '#' ){
            int dis = bfs( i, j );
            if( dis == INF ) continue;
            ans = max<int>( ans, dis );
        }
    printf("%d\n", ans);
}
 
int main(){
    scanf("%d%d", &h, &w);
    for(int i = 1; i <= h; ++i)
        scanf("%s", &G[ i ][ 1 ]);
    solve();
    return 0;
}