[BOJ] 소년 점프

Date:

[BOJ] 소년 점프

Problem URL : 소년 점프

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define p pair<int,int>
using namespace std;

int n, m;
char a[101][101];
int dist[101][101][3];
queue<p> q;
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

void bfs(int who) {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
            if (a[nx][ny] == '0' && dist[nx][ny][who] == -1) {
                q.push({ nx, ny});
                dist[nx][ny][who] = dist[x][y][who] + 1;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    memset(dist, -1, sizeof(dist));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]+1;
    }
    for (int i = 0; i < 3; i++) {
        int x, y;
        cin >> x >>y;
        q.push({ x, y,});
        dist[x][y][i] = 0;
        bfs(i);
    }
    int ans = 1e9, cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int nuksal = dist[i][j][0]; 
            int swings = dist[i][j][1]; 
            int changmo = dist[i][j][2];
            int time = max(max(nuksal, swings), changmo);
            if (min(min(nuksal, swings), changmo) != -1) {
                if (ans > time) {
                    ans = time;
                    cnt = 1;
                } else if (ans == time) {
                    cnt += 1;
                }
            }
        }
    }
    if (ans == 1e9) {
        cout << "-1\n";
    } else {
        cout << ans << endl << cnt;
    }
    return 0;
}

댓글