글 읽기 - 질문 있습니다 ....반례를 못찾겟습니다. ㅠㅠ

minjae200 5년 전 0

5 7 5 5
2000000 21111
1101000 11111
0010000 11111
1101000 11111
1101113 11113
output 6 output 4

4 4 4 4 4 4
2101 2000 2101
0101 1000 0101
0030 0113 0300
0000 1000 0000
output 3 output 4 output -2

4 4
2101
0101
0010
0030
output 4

5 6

000130

201101

100100

011000

100000

output 6

5 9

210101111

010000100

100000011

010000100

003011111

output -2

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

typedef struct {
	int y, x;
	int shape;
	int before;
	int py, px;
}Point;
int N, M, ans;
const int MAX = 500 + 1;
int map[MAX][MAX];
int dy[5] = {0, -1,1,0,0 };
int dx[5] = {0, 0,0,-1,1 };
pair<int,int> point[2];
bool visited[MAX][MAX][2];

bool checkRange(int y, int x, bool flag, int plusy, int plusx) 
{
	if (!flag) {
		if (1 <= y && y <= N && 1 <= x && x <= M) return true;
		else return false;
	}
	else {
		for (int i = -1; i <= 1; i++) {
			if (1 > y + plusy*i || y + plusy*i > N || 1 > x + plusx*i || x + plusx*i > M) return false;
		}
		return true;
	}
}

bool FindAnswer(Point cur)
{
	if (cur.y == point[1].first && cur.x == point[1].second) return true;
	if (cur.shape == 1) {
		for (int i = -1; i <= 1; i += 2) {
			if((cur.y + cur.py * i) ==  point[1].first &&
				(cur.x + cur.px * i) == point[1].second) return true;
		}
	}
	return false;
}

int BFS(void)
{
	queue<Point> q;
	visited[point[0].first][point[0].second][0] = true;
	Point temp = { point[0].first, point[0].second, 0, 0};
	q.push(temp);

	//1x3짜리 상자의 경우 ㅁㅁㅁ ㅁ
	//						   ㅁ
	//                         ㅁ       모두다 가운데칸을 기준으로 visited와 좌표를 구성하였습니다.
	while (!q.empty()) {
		int q_size = q.size();
		while (q_size--) {
			Point cur = q.front();
			q.pop();
			//정답을 찾았으면 바로 return (함수끝)
			if (FindAnswer(cur)) return ans;
			for (int i = 1; i <= 4; i++) {
				int next_y, next_x;
				//false면 1x1  true면 1x3으로 인식
				bool flag = false;  //상자 모양이 바꼈는지 (즉 1x1 -> 1x3      1x3 -> 1x1)
				bool changeflag = true;	//1x3상자가 1x3으로 유지됫는지 1x1인건지 check
				int plusy = 0, plusx = 0; //3칸을 올바르게 체크하기위한 변수 
				if (cur.shape == 0) {
					next_y = cur.y + dy[i] * 2;
					next_x = cur.x + dx[i] * 2;
					if (i == 1 || i == 2) plusy = 1, plusx = 0;
					else plusy = 0, plusx = 1;
					flag = true;
				}
				//3개짜리 블록을 그려놓고 생김새파악
				else if (cur.shape == 1) {
					//이전 블록이 상하에서 굴려졋는지
					if (cur.before == 1 || cur.before == 2) {
						//상하에대해
						if (i == 1 || i == 2) {
							next_y = cur.y + dy[i] * 2;
							next_x = cur.x + dx[i] * 2;
						}
						//좌우에대해
						else {
							next_y = cur.y + dy[i];
							next_x = cur.x + dx[i];
							changeflag = false;
							flag = true;
						}
						plusy = 1, plusx = 0;
					}
					//위와 반대케이스
					else if (cur.before == 3 || cur.before == 4) {
						if (i == 1 || i == 2) {
							next_y = cur.y + dy[i];
							next_x = cur.x + dx[i];
							changeflag = false;
							flag = true;
						}
						else {
							next_y = cur.y + dy[i]*2;
							next_x = cur.x + dx[i]*2;
						}
						plusy = 0, plusx = 1;
					}
				}
				//범위체크
				if (!checkRange(next_y, next_x, flag, plusy, plusx)) continue;
				//방문하였는지 체크
				if (visited[next_y][next_x][flag]) continue;
				//상자를 올릴수 있는지 체크하고 큐에넣어준다. (올릴수있으면)
				if (!flag) {//1x1상자는 그냥 그 위에 올릴수있을때 
					if (map[next_y][next_x] != 0) {
						visited[next_y][next_x][flag] = true;
						Point temp = { next_y, next_x, flag, i, plusy, plusx };
						q.push(temp);
					}
				}
				else {//1x3은 가운데 or 양끝에 올릴수있을대
					if (map[next_y][next_x] != 0 || 
						(map[next_y - plusy][next_x -plusx] != 0 && map[next_y + plusy][next_x + plusx] != 0)) {
						visited[next_y][next_x][flag] = true;
						Point temp = { next_y, next_x, flag, (changeflag) ? i : cur.before, plusy, plusx};
						q.push(temp);
					}
				}
			}
		}
		puts("");
		ans++;
	}
	return -2;
}

int main(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &map[i][j]);
			if (map[i][j] == 2) {
				point[0].first = i, point[0].second = j;
			}
			if (map[i][j] == 3) {
				point[1].first = i, point[1].second = j;
			}
		}
	}
	printf("%d\n", BFS());
	return 0;
}

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

문제

문제

출처

ICPC

질문 있습니다 ....반례를 못찾겟습니다. ㅠㅠ

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말