on
[3197] 백조의 호수
[3197] 백조의 호수
#include < bits / stdc + + .h >
using namespace std ;
typedef struct {
int y, x;
} state;
int n, m, l, r, dp[ 1501 ][ 1501 ], dy[ 4 ] = { 0 , 1 , 0 , - 1 }, dx[ 4 ] = { 1 , 0 , - 1 , 0 };
char a[ 1501 ][ 1501 ];
vector < state > pos;
queue < state > initq;
void init( void ) {
int i;
while ( ! initq.empty()) {
state cur = initq. front ();
initq. pop ();
for (i = 0 ; i < 4 ; i + + ) {
int y = cur.y + dy[i];
int x = cur.x + dx[i];
if (y < 0 | | x < 0 | | y > = n | | x > = m) continue ;
if (dp[y][x] = = - 1 ) {
dp[y][x] = dp[cur.y][cur.x] + 1 ;
initq.push({y, x});
r = max(dp[y][x], r);
}
}
}
return ;
}
bool check( int k) {
bool vst[ 1501 ][ 1501 ];
memset(vst, false , sizeof (vst));
queue < state > q;
int sy = pos[ 0 ].y, sx = pos[ 0 ].x;
q.push({sy, sx});
vst[sy][sx] = true ;
int i;
while ( ! q.empty()) {
state cur = q. front ();
q. pop ();
if (cur.y = = pos[ 1 ].y & & cur.x = = pos[ 1 ].x) {
return true ;
}
for (i = 0 ; i < 4 ; i + + ) {
int y = cur.y + dy[i];
int x = cur.x + dx[i];
if (y < 0 | | x < 0 | | y > = n | | x > = m) continue ;
if (vst[y][x] = = true | | dp[y][x] > k) continue ;
vst[y][x] = true ;
q.push({y, x});
}
}
return false ;
}
int main( void ) {
ios_base::sync_with_stdio( false );
cin .tie( 0 );
cout .tie( 0 );
cin > > n > > m;
memset(dp, - 1 , sizeof (dp));
int i, j;
for (i = 0 ; i < n; i + + ) {
for (j = 0 ; j < m; j + + ) {
cin > > a[i][j];
if (a[i][j] = = '.' ) {
dp[i][j] = 0 ;
initq.push({i, j});
}
if (a[i][j] = = 'L' ) {
dp[i][j] = 0 ;
initq.push({i, j});
pos. push_back ({i, j});
}
}
}
init();
int ans = 54321 ;
while (l < = r) {
int mid = (l + r) / 2 ;
bool res = check(mid);
if (res = = true ) {
ans = min(mid, ans);
r = mid - 1 ;
} else {
l = mid + 1 ;
}
}
cout < < ans;
return 0 ;
}
from http://dizlet.tistory.com/158 by ccl(A) rewrite - 2021-10-17 12:01:15