글 읽기 - 어디서 틀렸는지 모르겠습니다.

dbsah328 5년 전 0

예제 주어진거는 당연히 잘 출력되고 질문에 있는 여러 반례들도 다 바른 값이 출력되는데 제출하면 틀렸다고 뜨네여...뭐가 어디서 잘못되었는지;/

#include<stdio.h>
int arr[1005][1005];
int head;
int tail;
int ch[1005][1005];//벽 안 부순 경우의 체크
int ch1[1005][1005];//벽 부순 경우의 체크
int sum;
int dy[] = { 1, -1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int Ty, Tx;
typedef struct
{
	int x;//x좌표
	int y;//y좌표
	int z;//벽을 부수었는지 여부 1이면 부숨 0이면 안부숨
	int time;//시간
}asd;

asd Q[1000000];

int main()
{
	int N, M;
	int i, j, k;

	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			scanf("%1d", &arr[i][j]);
		}
	}
	Q[tail].x = 0;
	Q[tail].y = 0;
	Q[tail].z = 0;
	ch[Q[tail].y][Q[tail].x] = 1;
	Q[tail++].time = 1;
	while (head != tail)
	{
		if (Q[head].x == M - 1 && Q[head].y == N - 1)
		{
			if (head == 0)
			{
				printf("1");//혹시 그 자리가 바로 도착지인 경우
				return 0;
			}
			break;
		}
		for (k = 0; k < 4; k++)
		{
			Ty = Q[head].y + dy[k];//상하 이동경우
			Tx = Q[head].x + dx[k];//좌우 이동경우
			if (Ty >= 0 && Ty <= N - 1 && Tx >= 0 && Tx <= M - 1)
			{
				if (Q[head].z == 0)//벽을 안 부순 경우
				{
					if (arr[Ty][Tx] == 0 && ch[Ty][Tx] == 0)//갈 수 있고 들린적 없을 때
					{
						ch[Ty][Tx] = 1;//체크
                        ch1[Ty][Tx]=1;
						Q[tail].y = Ty;//좌표 저장
						Q[tail].x = Tx;//좌표 저장
						Q[tail].z = 0;//벽 부순여부
						Q[tail++].time = Q[head].time + 1;//이동거리
					}
					else if (arr[Ty][Tx] == 1 &&ch1[Ty][Tx]==0)//벽이고 들린적 없을 때
					{
						ch1[Ty][Tx] = 1;
						Q[tail].y = Ty;
						Q[tail].x = Tx;
						Q[tail].z = 1;
						Q[tail++].time = Q[head].time + 1;
					}
				}
				else if (Q[head].z!=0)//벽을 1번 부순 경우
				{
					if (arr[Ty][Tx] == 0 && ch1[Ty][Tx] == 0&&ch[Ty][Tx]==0)
					{
						ch1[Ty][Tx] = 1;
						Q[tail].y = Ty;
						Q[tail].x = Tx;
						Q[tail].z =1;
						Q[tail++].time = Q[head].time + 1;
					}
				}
			}
		}
		head++;
	}
	if (Q[head].time>=N+M-1&& Q[head].x == M - 1 && Q[head].y == N - 1)
	{
		printf("%d", Q[head].time);
	}
	else
		printf("-1");
	return 0;
}

dbsah328 5년 전 0

ㅂ변수 x랑 y를 아에 바꿔버리니깐맞는데

뭐가 문제인건가요...

#include<stdio.h>
int arr[1005][1005];
int head;
int tail;
int ch[1005][1005];//벽 안 부순 경우의 체크
int ch1[1005][1005];//벽 부순 경우의 체크
int sum;
int dy[] = { 1, -1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int Ty, Tx;
typedef struct
{
	int x;//x좌표
	int y;//y좌표
	int z;//벽을 부수었는지 여부 1이면 부숨 0이면 안부숨
	int time;//시간
}asd;

asd Q[1000000];

int main()
{
	int N, M;
	int i, j, k;

	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			scanf("%1d", &arr[i][j]);
		}
	}
	Q[tail].x = 0;
	Q[tail].y = 0;
	Q[tail].z = 0;
	ch[Q[tail].x][Q[tail].y] = 1;
	Q[tail++].time = 1;
	while (head != tail)
	{
		if (Q[head].y == M - 1 && Q[head].x == N - 1)
		{
			if (head == 0)
			{
				printf("1");//혹시 그 자리가 바로 도착지인 경우
				return 0;
			}
			break;
		}
		for (k = 0; k < 4; k++)
		{
			Ty = Q[head].y + dy[k];//상하 이동경우
			Tx = Q[head].x + dx[k];//좌우 이동경우
			if (Ty >= 0 && Ty <= M - 1 && Tx >= 0 && Tx <= N - 1)
			{
				if (Q[head].z == 0)//벽을 안 부순 경우
				{
					if (arr[Tx][Ty] == 0 && ch[Tx][Ty] == 0)//갈 수 있고 들린적 없을 때
					{
						ch[Tx][Ty] = 1;//체크
						ch1[Tx][Ty] = 1;
						Q[tail].y = Ty;//좌표 저장
						Q[tail].x = Tx;//좌표 저장
						Q[tail].z = 0;//벽 부순여부
						Q[tail++].time = Q[head].time + 1;//이동거리
					}
					else if (arr[Tx][Ty] == 1 &&ch1[Tx][Ty]==0)//벽이고 들린적 없을 때
					{
						ch1[Tx][Ty] = 1;
						Q[tail].y = Ty;
						Q[tail].x = Tx;
						Q[tail].z = 1;
						Q[tail++].time = Q[head].time + 1;
					}
				}
				else if (Q[head].z!=0)//벽을 1번 부순 경우
				{
					if (arr[Tx][Ty] == 0 && ch1[Tx][Ty] == 0&&ch[Tx][Ty]==0)
					{
						ch1[Tx][Ty] = 1;
						Q[tail].y = Ty;
						Q[tail].x = Tx;
						Q[tail].z =1;
						Q[tail++].time = Q[head].time + 1;
					}
				}
			}
		}
		head++;
	}
	if (Q[head].time>=N+M-1&& Q[head].y == M - 1 && Q[head].x == N - 1)
	{
		printf("%d", Q[head].time);
	}
	else
		printf("-1");
	return 0;
}

djm03178 5년 전 1

둘 다 위험한 코드입니다. 큐의 크기가 너무 작아서 그렇습니다. 1000*1000칸에 벽을 부순 상태와 안 부순 상태까지 총 200만개의 상태가 있을 수 있습니다.

위쪽 코드도 큐의 크기만 늘려주면 맞고, 아래쪽 코드가 맞은 건 배열을 훌쩍 넘어가도록 하는 데이터가 없거나, 넘어갔음에도 불구하고 운 좋게 맞은 것입니다.

dbsah328 5년 전 0

감사합니다...배열크기때문에 틀렸을 줄은 상상도 못했네요..

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다.

dbsah328 5년 전 0

dbsah328 5년 전 0

djm03178 5년 전 1

dbsah328 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말