백준 2589번 보물섬 ( C++ )

문제

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

2589번: 보물섬

 

해설

(50*50)* (50*50)의 경우의 수 이므로 1000만 이하이기 때문에 모든 정점에 대해 bfs를 돌며 최단거리 구하기

이때 첫 시작점을 1로 설정해줘야 첫 시작점으로 돌아가는 경우를 막을 수 있음 ( 결과에서 1 빼주기)

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, m, visited[54][54], ret;
vector<pair<int, int>> land;
char mp[54][54];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
 
void bfs(int y, int x)
{
  visited[y][x] = 1;
  queue<pair<int, int>> q;
  q.push({y, x});
  while (q.size())
  {
    tie(y, x) = q.front();
    q.pop();
    for (int i = 0; i < 4; i++)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx < 0 || ny < 0 || nx >= m || ny >= n || visited[ny][nx] || mp[ny][nx] == 'W')
        continue;
 
      visited[ny][nx] = visited[y][x] + 1;
      q.push({ny, nx});
      if (visited[ny][nx] > ret)
        ret = visited[ny][nx];
    }
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> mp[i][j];
      if (mp[i][j] == 'L')
        land.push_back({i, j});
    }
  }
 
  for (pair<int, int> l : land)
  {
    fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
    bfs(l.first, l.second);
  }
  cout << ret - 1;
}