글 읽기 - 테스트케이스 10개 이상 만들어보고 했는데 도저히 뭐가 틀린지 모르겠네요...

luckyhan1013 7년 전 0

그냥 일반적인 bfs 에서 경우에 맞는 visit 상태배열을 만들었습니다.

만들어본 테스트케이스는 모두 답이 나오고 예제도 나오는데 어디가 틀린걸까요...

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <iostream>
using namespace std;
#define INF 987654321

bool visit[105][105][4][4];
int map[105][105];
int SX, SY, SD;
int EX, EY, ED;
typedef struct point {
	int x, y, d, v, p;
};
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int M, N;

int bfs(point s) {
	queue<point> q;
	q.push(s);
	int ret = INF;
	while (!q.empty()) {
		point c = q.front();
		q.pop();
		if (visit[c.y][c.x][c.d][c.p] == true)
			continue;
		if (c.x == EX-1 && c.y == EY-1 && c.d == ED-1) {
			//printf("v=%d , p=%d \n", c.v,c.p);
			ret = min(ret,c.v);
			visit[c.y][c.x][c.d][c.p] = true;
			continue;
		}

		visit[c.y][c.x][c.d][c.p] = true;

		for (int i = 0; i < 4; i++) {
			if (c.d == i) {
				for (int j = 1; j <= 3; j++) {
					int xx = (dir[i][0] * j) + c.x;
					int yy = (dir[i][1] * j) + c.y;
					if (xx < 0 || yy < 0 || xx >= N || yy >= M)
						continue;
					if (map[yy][xx] == 1)
						break;
					point t;
					t.x = xx, t.y = yy, t.d = i, t.v = c.v + 1, t.p = j;
					q.push(t);
				}
			}
			else {
				point t = c;
				t.d = i, t.v = c.v + 1, t.p = 0;
				q.push(t);
			}
		}
	}

	return ret;
}

int main()
{
	scanf("%d%d", &M, &N);
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	scanf("%d%d%d", &SY, &SX, &SD);
	scanf("%d%d%d", &EY, &EX, &ED);

	point s;
	s.x = SX - 1, s.y = SY - 1, s.d = SD - 1, s.v = 0, s.p = 0;
	memset(visit, 0, sizeof(visit));
	printf("%d\n", bfs(s));

	return 0;
}