글 읽기 - 이제는 틀렸다고 하네요

vangard7 6년 전 0

q : 메인 Queue array 변수

qq : 임시 queue array 변수

(BFS 함수에서 발생가능한 숫자를 임시 queue에 반영, 해당함수의 메인 queue 끝나면, 임시qeue를 메인 queue로 옮겨줌)

nn : BFS 돌면서 발생하는 명령어 자리수

c : 특정숫자에서 발생하는 문자값 ( 1->D : 2인경우 c[2] = 'D')

p : BFS 에서 발생하는 이전 값 ( 1 -> D : 2 인경우 p[2] = 1)

샘플 3개는 맞는데 제출하면 틀렸다고 하네요 뭐가 잘못된걸까요?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int nn[10001], p[10001], v[10001];
char  c[10001];

int q[20001], qcnt;
int A, B;

void init()
{
	int i;

	for(i=0; i<10001; i++){
		nn[i] = 0;				
		v[i]  = 0;		
	}
}


int sortfn(const void *v1, const void *v2)
{
	int *a = (int *)v1;
	int *b = (int *)v2;
	return (*a - *b);
}

void input(int s, int k, char ch)
{
	if(nn[k] == 0 || nn[k] > nn[s]+1 ){
		nn[k] = nn[s]+1;
		p[k] = s;
		c[k] = ch;
	}	
}

void BFS()
{
	int i,j, k, r;
	int qq[40001], qqcnt=0;
	
	for(j=0; j<qcnt; j++){
		i = q[j];
		if(v[i]) continue;
								
		if((i*2)>10000) k = (i*2)%10000;
		else k = i*2;
		
		if(k != i)	{
			input(i, k, 'D');			
			qq[qqcnt++] = k;
		}				
		
		if( i==0 ) k = 9999;
		else k = i-1;
		if(k != i)	{
			input(i, k, 'S');
			qq[qqcnt++] = k;
		}
		
		k = i*10;
		k = k-(k/10000)*10000 + k/10000 ;
		if(k != i){
			input(i, k, 'L');
			qq[qqcnt++] = k;
		}
		
		r = i - (i/10)*10;
		k = r*1000 + i/10;
		if(k != i)	{
			input(i, k, 'R');
			qq[qqcnt++] = k;
		}
		v[i] =1;
	}
	
	qcnt = 0;
	for(i=0; i<qqcnt; i++){
		j = qq[i];
		
		if(v[j]) continue;
		
		q[qcnt] = j;
		qcnt++;
	}
}


void output()
{
	int i, k, e;	
	char r[10000];
	
	e = nn[B];
	k = B;
	r[e] = 0;
	for(i=0; i<e; i++){
		r[e-i-1] = c[k];
		k = p[k];		
	}
	
	printf("%s\n", r);
}

main() {
	int t, i, T, j;
		
	scanf("%d",   &T);
		
	for(t=1; t <= T; t ++){
		scanf("%d %d", &A, &B);

		init();
		q[0] = A;
		qcnt = 1;
		
		while(1){
			BFS();			
			
			if (nn[B]) {				
				output();
				break;
			}			
		}
	}
}		

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

문제

문제

출처

ICPC

이제는 틀렸다고 하네요

vangard7 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말