글 읽기 - 56퍼센트에서 틀리네요 ㅠㅠ

gxz94 6년 전 0

처음에는 53퍼센트에서 시간초과 나길래

BFS 과정에서 빙산 녹이는 과정으로 바꾸고...

모두 0일때 예외처리 추가 해서 넘겼는데

56퍼센트 쯤에서 틀렸다고 나오네요 ㅜㅜ

어떤 반례가 있을까요? ㅠ

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

int N,M;
int map[300][300];
int temp[300][300];
int visit[300][300];
int cnt=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int ans=0;
struct node
{
	int x;
	int y;
};
queue<node> q;
node start, tt;

bool chk ()
{
	for(int yy=0; yy<N; yy++)
	{
		for(int xx=0; xx<M; xx++)
		{
            if(cnt>=2)
		    return false;
			if(map[yy][xx]!=0)
				{ 
          			if(map[yy][xx-1]==0 && xx-1>=0 && xx-1<M)
						temp[yy][xx]--;
					 if(map[yy][xx+1]==0&& xx+1>=0 && xx+1<M)
						temp[yy][xx]--;
					 if(map[yy-1][xx]==0&&yy-1>=0 && yy-1<N)
						temp[yy][xx]--;
					 if(map[yy+1][xx]==0&&yy-1>=0 && yy-1<N)
						temp[yy][xx]--;
				}

			if(map[yy][xx]==0 || visit[yy][xx]>0)
				continue;
			
				start.x=xx;
				start.y=yy;
				q.push(start);
				cnt++;
				visit[start.y][start.x]=cnt;

				while(!q.empty())
				{
					start=q.front();
					q.pop();

                    if(map[start.y][start.x-1]!=0&& visit[start.y][start.x-1]==0 && (start.x-1)>=0 && (start.x-1)<M )
                    {
                        visit[start.y][start.x-1]=cnt;
							tt.x=start.x-1;
							tt.y=start.y;
							q.push(tt);
                    }	
					 if(map[start.y][start.x+1]!=0&& visit[start.y][start.x+1]==0 && (start.x+1)>=0 && (start.x+1)<M)
					{
                        visit[start.y][start.x+1]=cnt;
							tt.x=start.x+1;
							tt.y=start.y;
							q.push(tt);
                    }		
					 if(map[start.y-1][start.x]!=0&& visit[start.y-1][start.x]==0 && (start.y-1)>=0 && (start.y-1)<N )
					{
                        visit[start.y-1][start.x]=cnt;
							tt.x=start.x;
							tt.y=start.y-1;
							q.push(tt);
                    }		
					 if(map[start.y+1][start.x]!=0&& visit[start.y+1][start.x]==0 && (start.y+1)>=0 && (start.y+1)<N)
					{
                        visit[start.y+1][start.x]=cnt;
							tt.x=start.x;
							tt.y=start.y+1;
							q.push(tt);
                    }		
					
					
				}
			}
		}
	
	for(int yy=0; yy<N; yy++)
		{
			for(int xx=0; xx<M; xx++)
			{
				
				if(temp[yy][xx]>=0)
					map[yy][xx]=temp[yy][xx];
				else
					map[yy][xx]=0;
			}}

	 return true;

}

bool chk2()
{
	int ttt=0;
	for(int yy=0; yy<N; yy++)
	{
		for(int xx=0; xx<M; xx++)
		{
			ttt+=map[yy][xx];
		}
	}

	if(ttt==0)
		return false;
	else
		return true;
}
int main()
{
	cin>>N>>M;
	
	for(int yy=0; yy<N; yy++)
	{
		for(int xx=0; xx<M; xx++)
		{	
			cin>>map[yy][xx];
			temp[yy][xx]=map[yy][xx];
		}
	}



	while(chk() && chk2())
	{
		
		ans++; cnt=0;
		for(int i=0; i<N; i++)
			memset(visit[i], 0, sizeof(visit[i]));
	}

	cout<<ans<<endl;

	return 0; 
}

gxz94 6년 전 3

해결했습니다

문제 중 다 녹을때까지 덩어리가 쪼개지지 않으면 0을 출력한다라는 조건을 누락하였네요 ㅠㅠ

마지막에 정답 출력전에

다 녹았는가 && 덩어리 한개 인가 조건문을 추가해서 해결하였습니다!

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

문제

문제

출처

ICPC

56퍼센트에서 틀리네요 ㅠㅠ

gxz94 6년 전 0

gxz94 6년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말