글 읽기 - 도와주세요.....2267 단지번호

seanrocket17 6년 전 0

코드는 보시다시피 bfs코드이고요

visit[i][j]가 1이라는 것은 (i, j)를 방문했다는 뜻입니다

참고로 (i, j)에서 저는 i = 행, j = 열로 잡았습니다(헷갈릴 수 있으니 주의...)

혹시 코드에서 이상한 부분이나 틀린 테스트케이스 찾아주시면 매우매우매우매우감사!!!!!11

도와주세요!!!!!!!!

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
struct info{
    int x;
    int y;
};
 
queue <info> q;
bool visit[1000][1000];
int map[1000][1000];
int n, result[50], num = 2;
 
void bfs()
{
    while(!q.empty()){
        info cur = q.front();
        q.pop();
        if(visit[cur.x][cur.y]) continue;
        visit[cur.x][cur.y]=num;
        result[num]++;
        if(cur.x < n-1 && map[cur.x+1][cur.y] == 1 && !visit[cur.x+1][cur.y])
            q.push((info){cur.x+1, cur.y});
        if(cur.x > 0 && map[cur.x-1][cur.y] == 1 && !visit[cur.x-1][cur.y])
            q.push((info){cur.x-1, cur.y});
        if(cur.y < n-1 && map[cur.x][cur.y+1] == 1 && !visit[cur.x][cur.y+1])
            q.push((info){cur.x, cur.y+1});
        if(cur.y > 0 && map[cur.x][cur.y-1] == 1 && !visit[cur.x][cur.y-1])
            q.push((info){cur.x, cur.y-1});
    }
}
 
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            scanf("%d",&map[i][j]);
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (!visit[i][j] && map[i][j] == 1){
                q.push((info){i, j});
                bfs();
                num++;
            }
        }
    }
    printf("%d\n",num - 2);
    vector<int> ans;
    for (int i = 2; i < num; i++)
         ans.push_back(result[i]);
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size();i++)
        printf("%d\n",ans[i]);
    return 0;
}

moonhi123 6년 전 1

테스트 케이스는 돌려보셨나요?

먼저 입력부터가 scanf("%d",&map[i][j])로 되있어서 입력을 제대로 못받은것 같습니다.

입력받는것은 scanf("%1d",&map[i][j])로 바꾸셔야하는것 같습니다.

그리고 어떤의도로 info에 괄호를 쳐서 (info)이렇게 하신지 모르겠네요.

다른 케이스는 다 잘 돌아가는 것 같네요.

kdk8361 6년 전 1

25*25 맵이면 최대 625/2 대략 300개의 단지가 나올거 같습니다.

seanrocket17 6년 전 1

두 분 너무 감사합니다!!!!!!맞았습니다!!!!!!!!!!

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

문제

문제

출처

ICPC

도와주세요.....2267 단지번호

seanrocket17 6년 전 0

moonhi123 6년 전 1

kdk8361 6년 전 1

seanrocket17 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말