글 읽기 - 뭐가틀렸을까요 ..?

kimminsu6110 7년 전 0

제알고리즘은 4방향을 움직인다고 했을때, 현재 로봇의 방향이 움직이려는 방향과 같을때는 3번을 움직여 각각 큐에 넣어주고 , 움직임이 같지 않을때는 방향만 바꾼경우를 큐에넣어줘서 값을 구하는 알고리즘인데 . .무엇이 틀렸는지 전혀모르겠네요 .

혹시 고수님들의 도움을 얻을수있을까요 ? 부탁드립니다.

#include <stdio.h>

#define E 0
#define W 1
#define S 2
#define N 3
#pragma warning (disable:4996)
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int row;
int col;
int edx = 0;
int edy = 0;
int edr = 0;
int visit[102][102][4];
int arr[102][102];
int curQue = 0;

typedef struct node {
	int x;
	int y;
	int l;
	int dir;
}r;

r robot[100000];
void push(int a, int b, int c, int d)
{
	robot[curQue].x = a;
	robot[curQue].y = b;
	robot[curQue].l = c;
	robot[curQue].dir = d;
	curQue++;
}
void Input()
{
	int i = 0;
	int k = 0;
	int q = 0;
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &row, &col);
	for (i = 0; i < row; i++)
	{
		for (k = 0; k < col; k++)
		{
			scanf("%d", &arr[i][k]);
			for (q = 0; q < 4; q++)
			{
				visit[i][k][q] = 100000;
			}
		}
		
	}
	scanf("%d %d %d", &a, &b, &c);
	push(a - 1, b - 1, 0,c-1);
	visit[a - 1][b - 1][c - 1] = 1;
	scanf("%d %d %d", &a, &b, &c);
	edx = a - 1;
	edy = b - 1;
	edr = c - 1;
}

int rotate(int cd, int rd)
{
	if (cd == E)
	{
		if (rd == W) return 2;
		if (rd == S) return 1;
		if (rd == N) return 1;
	}
	else if (cd == W)
	{
		if (rd == E) return 2;
		if (rd == S) return 1;
		if (rd == N) return 1;
	}
	else if (cd == S)
	{
		if (rd == W) return 1;
		if (rd == E) return 1;
		if (rd == N) return 2;
	}
	else if(cd==N)
	{
		if (rd == W) return 1;
		if (rd == E) return 1;
		if (rd == S) return 2;
	}
}

void bfs()
{
	int rx = 0;
	int ry = 0;
	int rl = 0;
	int i = 0;
	int rdir = 0;
	int count = 0;
	int k = 0;

	while (count < curQue)
	{
		rdir = robot[count].dir;
		if (robot[count].x == edx && robot[count].y == edy )
		{
			printf("%d\n", robot[count].l+rotate(robot[count].dir,edr));
			return;
		}
		
		for (i = 0; i < 4; i++)
		{
			if (rdir == i)
			{
				rx = robot[count].x;
				ry = robot[count].y;
				rl = robot[count].l;
				for (k = 0; k < 3; k++)
				{
					rx += dx[i];
					ry += dy[i];
					if (rx < row && ry <col && rx> -1 && ry >-1 && arr[rx][ry] == 0 && visit[rx][ry][i] > rl+1)
					{
						push(rx, ry, rl + 1, i);
						visit[rx][ry][i] = rl+1;
					}
					else
					{
						break;
					}
					
				}
			}
			else
			{
				rx = robot[count].x;
				ry = robot[count].y;
				rl = robot[count].l;
				if (visit[rx][ry][i] > rl+rotate(rdir,i)&& arr[rx][ry] ==0)
				{
					push(rx, ry, rl + rotate(rdir, i), i);
					visit[rx][ry][i] = rl + rotate(rdir, i);
				}
			}
		}
		count++;
	}
}




int main()
{
	Input();
	bfs();
	return 0;
}

kimminsu6110 7년 전 0

방금 고쳐서 맞긴했는데 .. 이코드와 지금 제가 올린코드의 차이점이 if문안에들어있는데 break의 순서를 바꿔줬는데.. 뭐가다른걸까요 ?

#include <stdio.h>

#define E 0
#define W 1
#define S 2
#define N 3
#pragma warning (disable:4996)
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int row;
int col;
int edx = 0;
int edy = 0;
int edr = 0;
int visit[102][102][4];
int arr[102][102];
int curQue = 0;

typedef struct node {
	int x;
	int y;
	int l;
	int dir;
}r;

r robot[100000];
void push(int a, int b, int c, int d)
{
	robot[curQue].x = a;
	robot[curQue].y = b;
	robot[curQue].l = c;
	robot[curQue].dir = d;
	curQue++;
}
void Input()
{
	int i = 0;
	int k = 0;
	int q = 0;
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &row, &col);
	for (i = 0; i < row; i++)
	{
		for (k = 0; k < col; k++)
		{
			scanf("%d", &arr[i][k]);
			for (q = 0; q < 4; q++)
			{
				visit[i][k][q] = 100000;
			}
		}
		
	}
	scanf("%d %d %d", &a, &b, &c);
	push(a - 1, b - 1, 0,c-1);
	visit[a - 1][b - 1][c - 1] = 1;
	scanf("%d %d %d", &a, &b, &c);
	edx = a - 1;
	edy = b - 1;
	edr = c - 1;
}

int rotate(int cd, int rd)
{
	if (cd == E)
	{
		if (rd == W) return 2;
		if (rd == S) return 1;
		if (rd == N) return 1;
	}
	else if (cd == W)
	{
		if (rd == E) return 2;
		if (rd == S) return 1;
		if (rd == N) return 1;
	}
	else if (cd == S)
	{
		if (rd == W) return 1;
		if (rd == E) return 1;
		if (rd == N) return 2;
	}
	else if(cd==N)
	{
		if (rd == W) return 1;
		if (rd == E) return 1;
		if (rd == S) return 2;
	}
}

void bfs()
{
	int rx = 0;
	int ry = 0;
	int rl = 0;
	int i = 0;
	int rdir = 0;
	int count = 0;
	int k = 0;

	while (count < curQue)
	{
		rdir = robot[count].dir;
		if (robot[count].x == edx && robot[count].y == edy && robot[count].dir == edr)
		{
		printf("%d\n", robot[count].l);
		return;
		}
		
		for (i = 0; i < 4; i++)
		{
			if (rdir == i)
			{
				rx = robot[count].x;
				ry = robot[count].y;
				rl = robot[count].l;
				for (k = 0; k < 3; k++)
				{
					rx += dx[i];
					ry += dy[i];
					if (rx >= row || ry >= col || rx< 0 || ry < 0 || arr[rx][ry] == 1 || visit[rx][ry][i] < rl+1)
					{
						break;
					}
					else
					{
						push(rx, ry, rl + 1, i);
						visit[rx][ry][i] = rl+1;
					}
					
				}
			}
			else
			{
				rx = robot[count].x;
				ry = robot[count].y;
				rl = robot[count].l;
				if (visit[rx][ry][i] > rl+rotate(rdir,i)&& arr[rx][ry] ==0)
				{
					push(rx, ry, rl + rotate(rdir, i), i);
					visit[rx][ry][i] = rl + rotate(rdir, i);
				}
			}
		}
		count++;
	}
}




int main()
{
	Input();
	bfs();
	return 0;
}

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

문제

문제

출처

ICPC

뭐가틀렸을까요 ..?

kimminsu6110 7년 전 0

kimminsu6110 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말