글 읽기 - 반례를 모르겠습니다 ㅠㅠ

sm970124 6년 전 0

어디가 틀린걸까요 ㅠㅠ 반례를 알려주세요 ㅠㅠ

#include<stdio.h>
#define max 201
struct r
{
	int x;
	int y;
	int con;
	int via;
}q[max*max*31];
int k, w, h, c[max][max][31],st,ed;
void qq()
{
	int X,Y,C,xx[4] = { 0,0,1,-1 }, yy[4] = { 1,-1,0,0 }, dx[8] = { 1,1,-1,-1,2,2,-2,-2 }, dy[8] = {2,-2,2,-2,1,-1,1,-1},i;
	st = ed = -1;
	q[++st].x = 1;
	q[st].y = 1;
	q[st].via = 0;
	q[st].con = 0;
	while(st!=ed)
	{
		X = q[++ed].x;
		Y = q[ed].y;
		C = q[ed].con;
		if (X == w&&Y == h)//w은 가로h는 세로
		{
			printf("%d", q[ed].via);
			break;
		}
		for (i = 0; i < 4; i++)
		{
			if (X + xx[i] <= 0 || X + xx[i] > w || Y + yy[i] <= 0 || Y + yy[i] > h)continue;
			if (c[Y + yy[i]][X + xx[i]][C] == 1)continue;
			q[++st].x = X + xx[i];
			q[st].y = Y + yy[i]; 
			c[Y + yy[i]][X + xx[i]][C] = 1;
			q[st].via = q[ed].via + 1;
		}
		if (C < k)
		{
			for (i = 0; i < 8; i++)
			{
				if (X + dx[i] <= 0 || X + dx[i] > w || Y + dy[i] <= 0 || Y + dy[i] > h)continue;
				if (c[Y + dy[i]][X + dx[i]][C+1] == 1)continue;
				q[++st].x = X + dx[i];
				q[st].y = Y + dy[i];
				c[Y + dy[i]][X + dx[i]][C+1] = 1;
				q[st].con = C + 1;
				q[st].via = q[ed].via + 1;
			}
		}
	}
}
int main()
{
	int i, j,k1;
	scanf("%d", &k);
	scanf("%d %d", &w, &h);//w은 가로h는 세로
	for (i = 1; i <= h; i++)
	{
		for (j = 1; j <= w; j++)
		{
			scanf("%d", &c[i][j][0]);
			for (k1 = 1; k1 <= k; k1++)
			{
				c[i][j][k1] = c[i][j][0];
			}
		}
	}
	for (k1 = 0; k1 <= k; k1++)
	{
		c[1][1][k1] = 1;
	}
	qq();
	if (q[ed].x != w || q[ed].y != h)printf("-1");
	return 0;
}

sukwoo0711 6년 전 1

1
5 5
0 1 1 0 1
0 0 1 0 1
0 1 0 1 1
0 1 0 1 0
1 1 0 1 0

==========> output : 6

answer = -1

sm970124 6년 전 0

감사합니다

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

문제

문제

출처

ICPC

반례를 모르겠습니다 ㅠㅠ

sm970124 6년 전 0

sukwoo0711 6년 전 1

sm970124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말