[BOJ 2589] 보물섬

백준 :: BOJ :: 2589 :: 보물섬

출처 :  https://www.acmicpc.net/problem/2589

#include <iostream>

#include <memory.h>

#include <algorithm>

#include <queue>

using namespace std;

int N, M, ans;

int map[50][50];

int depth[50][50];

bool visited[50][50];

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

queue <pair<int,int>> q;

inline bool check(int i, int j) { return ((i>=0 && j>=0 && i<N && j<M 

&& !visited[i][j]&&map[i][j]) ? true : false); }

void bfs(int i, int j) {

visited[i][j] = true;

q.push(make_pair(i,j));

int ii, jj;

while (!q.empty()) {

ii = q.front().first; jj = q.front().second; q.pop();

for (int d = 0; d < 4; d++) {

int ni = ii + dir[d][0]; int nj = jj + dir[d][1];

if (check(ni, nj)) {

visited[ni][nj] = true;

q.push(make_pair(ni, nj));

depth[ni][nj] = depth[ii][jj] + 1;

ans = max(ans, depth[ni][nj]);

}

}

}

}

int main() {

cin >> N >> M; ans = 0;

char c;

for (int i = 0; i < N; i++) {

for (int j = 0; j < M; j++) {

cin >> c; map[i][j] = (c == 'L' ? 1 : 0);

}

}

for (int i = 0; i < N; i++) {

for (int j = 0; j < M; j++) {

if (map[i][j]) {

bfs(i, j);

memset(visited, 0, sizeof(visited));

memset(depth, 0, sizeof(depth));

}

}

}

cout << ans << endl;

return 0;

}