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;
}
```