[백준] 17086번: 아기 상어2

17086번: 아기 상어 2

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX 51
using namespace std;

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

int n, m;
int map[MAX][MAX];
int visit[MAX][MAX];
vector<int>pos;

void bfs(int a, int b) {

	for (int i = 1;i < MAX;i++) {
		for (int j = 1;j <MAX;j++) {
			visit[i][j] = false;
		}
	}

	vector<int>calc;
	queue<pair<int, int>>q;
	queue<int>dis;

	q.push(make_pair(a, b));
	dis.push(0);
	visit[a][b] = true;

	while (!q.empty()) {

		int y = q.front().first;
		int x = q.front().second;
		int d = dis.front();
		q.pop(); dis.pop();

		if (map[y][x] == 1 && d != 0) {
			calc.push_back(d);
			break;
		}
	

		for (int i = 0;i < 8;i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (visit[ny][nx]) continue;
			if (ny < 1 || nx<1 || ny>n || nx>m) continue;
			visit[ny][nx] = true;

			q.push({ ny,nx }); dis.push(d + 1);
		}
	}

	int temp = *min_element(calc.begin(), calc.end());
	pos.push_back(temp);

}

int main() {

	cin >> n >> m;

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			if(map[i][j]!=1) bfs(i, j);
		}
	}

	int ans = *max_element(pos.begin(), pos.end());
	cout << ans;
}