글 읽기 - DFS 로 풀고, 나온 TC 는 다 통과하는데. 틀렸다고 나오네요.

neogates 5년 전 0

DFS 로 풀어봤습니다.

코드는 아무리 봐도 문제가 없어보이고. 문제 특성상 TC 는 제가 직접 만들기 어려워서

아래 누가 올려주신 TC 로 50x50 까지 다 통과하는거 확인했는데.

답은 틀렸다고 나오네요.

혹시 오류 지적해주실 분 계실까요?

#include <iostream>
#include <string.h>
using namespace std;

int C,R;
int wall[51][51];
int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
int room_check[51][51];
int my_room[2500] ={0,};
bool room_link[2500][2500];// ={0,};
void dfs(int row, int col, int num)
{
	int check = wall[row][col];
	int nr, nc;
	room_check[row][col] = num;
	for(int i=0;i<4;i++)
	{
		nr = row+dir[i][0];
		nc = col+dir[i][1];
		int avail =check;
		for(int j=0;j<i;j++)
		{
			avail = avail >> 1;
		}
		bool go = avail & 1;
		if(nr>=0 && nr<R && nc>=0 && nc <C )
		{
			if(!go && room_check[nr][nc] ==0 )
			{
				dfs(nr,nc, num);
			}
			else
			{
				room_link[num][room_check[nr][nc]] = 1;
				room_link[room_check[nr][nc]][num] = 1;
			}
		}
	}
}
int main(int argc, char** argv) {

	memset(room_link, 0x00, sizeof(bool)*2500*2500);
	memset(room_check, 0x00, sizeof(int)*51*51);
	cin >> C >> R;
	
	for(int i=0;i<R;i++)
	{
		for(int j=0;j<C;j++)
		{
			cin >> wall[i][j] ;
		}
	}
	int num = 0;
	for(int i=0;i<R;i++)
	{
		for(int j=0;j<C;j++)
		{
			if(room_check[i][j] == 0)
			{
				num++;			
				dfs(i,j,num);
			}
		}
	}
	for(int i=0;i<R;i++)
	{
		for(int j=0;j<C;j++)
		{
			my_room[room_check[i][j]]++;
		}
	}
	int result = 0;
	int mx_room =0;
	for(int i=1;i<=num;i++)
	{
		mx_room = max(mx_room,my_room[i]);
		for(int j=i+1;j<=num;j++)
		{
			if(room_link[i][j])
			{
				result = max(result,my_room[i] + my_room[j] );
			}
		}
	}	
	printf("%d\n",num);
	printf("%d\n",mx_room);
	printf("%d\n",result);
	return 0;
}

zhh1020 5년 전 1

저도 동일한 경우였는데요 맵 사이즈를 두배늘리고 방의 개수를 세주는 배열의 크기를 늘렸더니 통과했습니다.

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

문제

문제

출처

ICPC

DFS 로 풀고, 나온 TC 는 다 통과하는데. 틀렸다고 나오네요.

neogates 5년 전 0

zhh1020 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말