글 읽기 - 반례좀 부탁드리겠습니다

nx20028 4년 전 0

착각할 만한 반례가 있을까요?

부탁드립니다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int r,c;
int map[501][501];
int ballNum[501*501];
int dest[501][501];

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

void init(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>map[i][j];
        }
    }
}

int dfs(int y,int x){ //(y,x)에 최초에 있던 1개의 공의 최종 목적지를 찾는 함수

    int& ref = dest[y][x];
    if(ref) return ref;

    int fy=-1;
    int fx=-1;
    int cmp=200000000;

    for(int i=0;i<8;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(ny<1 || ny>r || nx<1 || nx>c)continue;
        if(map[ny][nx]>map[y][x])continue;
        if(cmp>map[ny][nx]){
            cmp=map[ny][nx];
            fy=ny;
            fx=nx;
        }
    }

    if(fy==-1 && fx==-1){
        dest[y][x]=(y-1)*r+x;
        return dest[y][x];
    }

    dest[y][x]=dfs(fy,fx);
    return dest[y][x];
}

void solution(){
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ballNum[dfs(i,j)]+=1;
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cout<<ballNum[(i-1)*r+j]<<" ";
        }
        cout<<"\n";
    }
}

int main(){
    init();
    solution();
}

unused 4년 전 0

2 3

4 5 6

1 2 3

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

문제

문제

출처

ICPC

반례좀 부탁드리겠습니다

nx20028 4년 전 0

unused 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말