글 읽기 - 반례 부탁드립니다

seoin1415 2년 전 0

다리 만들기 85%에서 계속 틀렸다고 나옵니다.게시판에 있는 반례들은 전부 통과하는데 뭐가 무엇인지 모르겠습니다.

#include <stdio.h>
#include <queue>
using namespace std;
int arr[101][101];
int n;
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};
int visit[101][101];
int visit2[101][101];
int visit3[101][101];
int cnt = 1;
queue < pair<int,int> > q;
queue < pair < pair <int,int>,int > > q2;
int safe(int x,int y)
{
	return x >= 0 && x < n && y >= 0 && y < n;
}

void bfs(int x,int y)
{
	int i,j,xx,yy;
	q.push({x,y});
	visit[x][y] = cnt;
	while(!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		//printf("x=%d y=%d\n",x,y);
		q.pop();
		for(i=0;i<4;i++)
		{
			xx = x + dx[i];
			yy = y + dy[i];
			if(safe(xx,yy) && visit[xx][yy] == 0 && arr[xx][yy] == 1)
			{
				q.push({xx,yy});
				visit[xx][yy] = cnt;
			}
		}
	}
}

void solve()
{
	int i,j,k,xx,yy,x,y,z;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(arr[i][j] == 1 && visit[i][j] == 0)
			{
				bfs(i,j);
				cnt++;		
			}
		}
	}
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(visit[i][j] > 0)
			{
				for(k=0;k<4;k++)
				{
					xx = i + dx[k];
					yy = j + dy[k];	
					if(safe(xx,yy) && arr[xx][yy] == 0 && visit3[xx][yy] > 0 && visit3[xx][yy] != visit[i][j])
					{
						//printf("i=%d j=%d xx=%d yy=%d\n",i,j,xx,yy);
						printf("1");
						return;
					}
					if(safe(xx,yy) && arr[xx][yy] == 0 && visit3[xx][yy] == 0)
					{
						q2.push({{xx,yy},visit[i][j]});
						visit3[xx][yy] = visit[i][j];
						visit2[xx][yy] = 1;
						//printf("i=%d j=%d xx=%d yy=%d\n",i,j,xx,yy);
					}
				}
			}
		}
	}
	
	
	
	while(!q2.empty())
	{
		x = q2.front().first.first;
		y = q2.front().first.second;
		z = q2.front().second;
		q2.pop();
		//printf("!!!X:%d Y:%d Z:%d\n",x,y,z);
		for(i=0;i<4;i++)
		{
			xx = x + dx[i];
			yy = y + dy[i];
			if(safe(xx,yy) && visit[xx][yy] != z && visit3[xx][yy] != z)
			{
				//printf("XX:%d YY:%d VISIT:%d\n",xx,yy,visit2[xx][yy]);
				if(arr[xx][yy] > 0)
				{
					//printf("x=%d y=%d visit2=%d\n",x,y,visit2[x][y]);
					printf("%d",visit2[x][y]);
					return;
				}
				else 
				{
					q2.push({{xx,yy},z});
			
					visit2[xx][yy] = visit2[x][y] + 1;	
					visit3[xx][yy] = z;			
				}
			}
		}
	}
}

int main()
{
	
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			scanf("%d",&arr[i][j]);
		}
	}
	solve();
	return 0;
}
/*
5

1 0 0 0 0

1 0 0 0 1

1 1 1 0 1

0 0 0 0 0

0 0 0 1 0*/

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

문제

문제

출처

ICPC

반례 부탁드립니다

seoin1415 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말