글 읽기 - 어디가 틀린지 못찾겠어요ㅠㅠㅠㅠㅠㅠ

zxc5430 5년 전 0

만들어본 예시 찾아봐도 돌아가고 사람들 코드랑 비교해봐도 아이디어 비슷하게 짠거같은데 계속 틀렸습니다가 떠요ㅠㅠㅠㅠㅠㅠ

#include<stdio.h>
int n, m;
char c[55][55];
int map[55][55];
int check[55][55];
int st;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
#define f 1000000000

struct MyStruct
{
	int x, y;
	int a;
}q[3000], s, e, tp;

void up(int a) // 우선순위 큐 삽입
{
	while (a > 1)
	{
		if (q[a / 2].a > q[a].a)
		{
			tp = q[a / 2];
			q[a / 2] = q[a];
			q[a] = tp;
			a /= 2;
		}
		else
		{
			return;
		}
	}
}

void down() // 우선순위 큐 삭제
{
	q[1] = q[st];
	q[st--].a = f; // 오른쪽 노드 비어있을 때를 위한 초기화

	int a = 1;

	while (a * 2 <= st)
	{
		if (q[a * 2].a < q[a * 2 + 1].a)
		{
			if (q[a * 2].a < q[a].a)
			{
				tp = q[a];
				q[a] = q[a * 2];
				q[a * 2] = tp;
				a *= 2;
			}
			else
				return;
		}
		else
		{
			if (q[a * 2 + 1].a < q[a].a)
			{
				tp = q[a];
				q[a] = q[a * 2 + 1];
				q[a * 2 + 1] = tp;
				a *= 2 + 1;
			}
			else
				return;
		}
	}
}

void bfs()
{
	int x, y, i, a, b, c, d;
	q[++st].x = s.x;
	q[st].y = s.y;
	check[s.x][s.y] = 0;

	while (st)
	{
		a = q[1].x;
		b = q[1].y;
		c = q[1].a;

		if (a == e.x && b == e.y)
		{
			printf("%d %d", check[a][b] / 10000, check[a][b] % 10000); // 가중치값으로 나눠서 값 구하기
			return;
		}

		for (i = 0; i < 4; i++)
		{
			x = a + dx[i];
			y = b + dy[i];

			if (x > 0 && y > 0 && x <= n && y <= m && check[x][y] > c + map[x][y]) // 현재 가중치+맵가중치<가려고 하는 자리의 값 보다 작을때
			{
				q[++st].x = x;
				q[st].y = y;
				q[st].a = c + map[x][y];
				check[x][y] = c + map[x][y];
				up(st);
			}
		}
		down();

	}
}

int main()
{
	int i, j, k;
	int x, y;
	scanf("%d%d", &n, &m);

	for (i = 1; i <= n; i++)
		scanf("%s", &c[i][1]);

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			if (c[i][j] == 'g')
			{
				map[i][j] = 10000;   //쓰레기 위치엔 가중치 10000
				for (k = 0; k < 4; k++)
				{
					x = i + dx[k];
					y = j + dy[k];
					if (c[x][y] == '.')
					{
						map[x][y] = 1; //쓰레기 주변엔 가중치 1
					}
				}
			}

			if (c[i][j] == 'F')
			{
				e.x = i;
				e.y = j;
			}

			if (c[i][j] == 'S')
			{
				s.x = i;
				s.y = j;
			}
			check[i][j] = f;  // 맵 초기화
		}
	}


	bfs();
}

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

문제

문제

출처

ICPC

어디가 틀린지 못찾겠어요ㅠㅠㅠㅠㅠㅠ

zxc5430 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말