글 읽기 - 혹시 반례가 있을까요?

walker123 3년 전 0

테스트 케이스는 다 맞았는데, 틀렸다고 나옵니다.

DFS 백트레킹으로 풀었고, Depth가 증가하기 전에, Solve 함수 내에서 배열을 선언해서

Copy 하고 백트레킹이 종료되어 반환할 경우에, 다시 배열 정보를 불려오는 형식으로 풀었습니다만,

예제는 다 맞았는데, 제출하니 틀렸다고 나옵니다.

방향이나, 물고기 인덱싱은 1부터 시작합니다.

혹시 반례를 얻을 수 있을까요???

#include <iostream>
using namespace std;

typedef struct
{
	int x;
	int y;
	int dir;
	bool live;
}fish_t;

int dx[] = { 0,-1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,0,-1,-1,-1,0,1,1,1 };
int map[4][4];
int shark_dir;
int shark_x, shark_y;
int ans;
fish_t fish[17];

void _init()
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			int input1, input2;
			cin >> input1 >> input2;
			map[i][j] = input1;
			fish[input1].x = i;
			fish[input1].y = j;
			fish[input1].dir = input2;
			fish[input1].live = true;
		}
	}
	return;
}

int _catch_fish(int x, int y)
{
	int idx = map[x][y];
	shark_dir = fish[idx].dir;
	shark_x = x;
	shark_y = y;
	fish[idx].live = false;
	map[x][y] = 0;
	return idx;
}

void _move_fish()
{
	for (int i = 1; i <= 16; i++)
	{
		if (false == fish[i].live)continue;
		int nx, ny;
		while (1)
		{
			nx = fish[i].x + dx[fish[i].dir];
			ny = fish[i].y + dy[fish[i].dir];
			if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || (nx == shark_x && ny == shark_y))
			{
				fish[i].dir += 1;
				if (9 == fish[i].dir)fish[i].dir = 1;
			}
			else break;
		}
		if (0 == map[nx][ny])
		{
			map[fish[i].x][fish[i].y] = 0;
			fish[i].x = nx;
			fish[i].y = ny;
			map[nx][ny] = i;
		}
		else
		{
			fish[map[nx][ny]].x = fish[i].x;
			fish[map[nx][ny]].y = fish[i].y;
			map[fish[i].x][fish[i].y] = map[nx][ny];
			fish[i].x = nx;
			fish[i].y = ny;
			map[nx][ny] = i;
		}
	}
	return;
}

bool _check()
{
	int nx = shark_x + dx[shark_dir];
	int ny = shark_y + dy[shark_dir];
	if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || map[nx][ny] == 0)return true;
	else return false;
}

void _copy_context(int(*temp_map)[4], fish_t* temp_fish)
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			temp_map[i][j] = map[i][j];
		}
	}
	for (int i = 1; i <= 16; i++)
	{
		temp_fish[i] = fish[i];
	}
	return;
}

void _return_context(int(*temp_map)[4], fish_t* temp_fish)
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			map[i][j] = temp_map[i][j];
		}
	}
	for (int i = 1; i <= 16; i++)
	{
		fish[i] = temp_fish[i];
	}
	return;
}

void _solve(int x, int y, int sum)
{
	sum += _catch_fish(x, y);
	if (_check())
	{
		if (ans < sum)ans = sum;
		return;
	}
	int temp_map[4][4];
	fish_t temp_fish[17];


	_move_fish();
	_copy_context(temp_map, temp_fish);

	for (int i = 1; i <= 3; i++)
	{
		int nx = shark_x + (i * dx[shark_dir]);
		int ny = shark_y + (i * dy[shark_dir]);
		if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)break;
		if (map[nx][ny] == 0)continue;

		int temp_shark_dir = shark_dir;
		int temp_shark_x = shark_x, temp_shark_y = shark_y;

		_solve(nx, ny, sum);
		shark_dir = temp_shark_dir;
		shark_x = temp_shark_x;
		shark_y = temp_shark_y;

		_return_context(temp_map, temp_fish);
	}
	return;
}

int main(int argc, char** argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	_init();
	_solve(0, 0, 0);
	cout << ans << '\n';
	return 0;
}

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

문제

문제

출처

ICPC

혹시 반례가 있을까요?

walker123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말