글 읽기 - 왜 틀렸는지 이유를 모르겠습니다..

specimen 5년 전 0

bfs로 대륙 번호를 매기고

다시 bsf로 (dist함수)로 거리를 쟀습니다.

음.. 다른 예를 들어도 정답이 잘 나오는데 틀렸다고 나옵니다.

이유를 알 수 있을까요?

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <utility>
#include <string.h>
using namespace std;
const int dy[4] = {0, 0, -1, 1};
const int dx[4] = {-1, 1, 0, 0};
int map[101][101];
int check[101][101];
int ch[101][101];
int n, cnt = 1;
void bfs(int startY, int startX){
    queue<pair<int, int>> q;
    q.push(make_pair(startY, startX));
    check[startY][startX] = cnt;
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(yy >= 0 && xx >= 0 && yy < n && xx < n){
                if(check[yy][xx] == 0 && map[yy][xx] == 1){
                    q.push(make_pair(yy, xx));
                    check[yy][xx] = cnt;
                }
            }
        }
    }
    cnt++;
}
int dist(int sY, int sX, int c){
    memset(ch, -1, sizeof(ch));
    queue<pair<int, int>> q;
    q.push(make_pair(sY, sX));
    ch[sY][sX] = 0;
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < n && xx >= 0 && x < n) {
                if (check[yy][xx] != 0 && check[yy][xx] != c) {
                    return ch[y][x];
                }
                if (check[yy][xx] == 0 && ch[yy][xx] == -1) {
                    ch[yy][xx] = ch[y][x] + 1;
                    q.push(make_pair(yy, xx));
                }
            }
        }
    }
}
int main(){
    int m = 1111, c = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> map[i][j];
            check[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(map[i][j] == 1 && check[i][j] == 0){
                bfs(i, j);
            }
        }
    }
    int ans = 987654321;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(check[i][j]) {
                ans = min(ans, dist(i, j, check[i][j]));
            }
        }
    }
    cout << ans << '\n';
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸는지 이유를 모르겠습니다..

specimen 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말