글 읽기 - 반례가 뭔지 모르겠습니다.ㅠㅠㅠㅠ도와주세요

zas777 4년 전 0

어디서 틀린지 전혀 감이 안옵니다.

dfs하는 부분은 맞는 것 같은데요...

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int Map[101][101];
int visit[101][101];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int cnt=1;
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(0<=nx&&nx<n&&0<=ny&&ny<n){
			if(Map[nx][ny]&&visit[nx][ny]==0){
				visit[nx][ny]=1;
				Map[nx][ny]=cnt;
				dfs(nx,ny);
			}
		}

	}
}
int bfs(int cnt){
	queue<pair<int,int>> q;
	int nx,ny,x,y;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(Map[i][j]==cnt){
				visit[i][j]=1;
				q.push(make_pair(i,j));
			}
		}
	}
	int result=0;
	while(!q.empty()){
		int Qsiz=q.size();
		for(int k=0;k<Qsiz;k++){
			x=q.front().first;
			y=q.front().second;
			q.pop();
			for(int i=0;i<4;i++){
				nx=x+dx[i];
				ny=y+dy[i];
				if(0<=nx&&nx<n&&0<=ny&&ny<n){
					if(Map[nx][ny]&&Map[nx][ny]!=cnt){
						return result;
					}else if(Map[nx][ny]==0&&visit[nx][ny]==0){
						visit[nx][ny]=1;
						q.push(make_pair(nx,ny));
					}
				}
			}
		}
		result++;
		
	}
	return result;
}
int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>Map[i][j];
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(Map[i][j]&&visit[i][j]==0){
				dfs(i,j);
				cnt++;
			}
		}
	}
	int Min=987654321;
	for(int i=1;i<cnt;i++){
		memset(visit,0,sizeof(visit));
		Min=min(Min,bfs(i));

	}
	cout<<Min<<'\n';
	return 0;
}

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

문제

문제

출처

ICPC

반례가 뭔지 모르겠습니다.ㅠㅠㅠㅠ도와주세요

zas777 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말