글 읽기 - 예제케이스 다해봤습니다 도와주세요..

rkdgh98 4년 전 0

GCPC 시크릿 TC도 다 대입해봤는데 결과에는 이상이 없고, 시간초과도 아닌 것 같은데 대체 뭐가 틀린건지 잘 모르겠습니다.

dfs 사용해보았구요, check를 사용해서 최대한 필요없는 탐색은 줄였습니다.

TC는 다 맞으니까 뭐가 틀린지 모르겠어서 참 답답합니다 ㅜㅜ

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

struct xy{
	int x;
	int y;
};

xy gs[100];
xy st, fes;
stack<int> s;
int n;
int check[100];

int dfs(xy now,int ind)
{
	check[ind]++;
	if((abs(now.x-fes.x)+abs(now.y-fes.y))<=1000) return 1;
	
	for(int i=0;i<n;i++)
	{
		if(check[i]==0&&(abs(now.x-gs[i].x)+abs(now.y-gs[i].y))<=1000)
		s.push(i);
	}
	while(!s.empty())
	{
		int qwe = s.top();
		s.pop();
		if(check[qwe]) continue;
		if(dfs(gs[qwe],qwe)) return 1;
	}
	return 0;
}

int main() {
	cin.tie(NULL);ios_base::sync_with_stdio(false);
	int t; cin>>t;
	for(int i=0;i<t;i++)
	{
		memset(check,0,sizeof(check));
		cin>>n>>st.x>>st.y;
		int ans=0;
		for(int j=0;j<n;j++)
		{
			cin>>gs[j].x>>gs[j].y;
		}
		cin>>fes.x>>fes.y;
		if(n==0)
		{
			if(abs(fes.x-st.x)+abs(fes.y-st.y)<=1000)
			{
				cout<<"happy\n"; continue;
			}
			else
			{
				cout<<"sad\n"; continue;
			}
		}
		
		for(int j=0;j<n;j++)
		{
			if(check[j]==0&&(abs(gs[j].x-st.x)+abs(gs[j].y-st.y)<=1000))
			{
				if(dfs(gs[j],j)) {ans=1; break;}
			}
		}
		if(ans) cout<<"happy\n";
		else cout<<"sad\n";
	}
	return 0;
}

djm03178 4년 전 1

반례입니다.

1
1
0 0
9999 9999
0 1

output: sad
answer: happy

rkdgh98 4년 전 0

감사합니다.

고치다보니 테스트케이스마다 스택을 안비우고 있는 실수도 발견했네요 ㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

예제케이스 다해봤습니다 도와주세요..

rkdgh98 4년 전 0

djm03178 4년 전 1

rkdgh98 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말