글 읽기 - 반례를 찾았으나 해결법을 모르겠습니다.

bgjuw12 5년 전 0

질문게시판을 뒤져가며 모든 반례를 대입하면서 코드를 수정했는데

어떤 반례하나에서 막혀서 계속 헤메고 있습니다

조언 부탁드립니다.

6 5
2 2 6 0 5
0 6 6 0 4
6 6 0 0 0
2 6 4 6 0
6 3 0 0 6
6 4 0 6 6

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> camera;
vector<pair<int, int>> camera_point;
int M, N, num, result = 10000, temp = 0;

int (*right(int x, int y, int office_temp[][9]))[9]
{
	while (y + 1< M && office_temp[x][y + 1] != 6 )
	{
		if (office_temp[x][y+1] == 0)
		{
			office_temp[x][++y] = 9;
		}
		else
		{
			++y;
		}
	}
	return office_temp;
}

int (*down(int x, int y, int office_temp[][9]))[9]
{
	while (x + 1 < N && office_temp[x + 1][y] != 6)
	{
		if (office_temp[x+1][y] == 0)
		{
			office_temp[++x][y] = 9;
		}
		else
		{
			x++;
		}
	}
	return office_temp;
}

int (*left(int x, int y, int office_temp[][9]))[9]
{
	while (y - 1 > -1 && office_temp[x][y - 1] != 6)
	{
		if(office_temp[x][y-1] ==0) 
		{
			office_temp[x][--y] = 9;
		}
		else
		{
			y--;
		}
	}
	return office_temp;
}

int (*up(int x, int y, int office_temp[][9]))[9]
{
	while (x - 1 > -1 && office_temp[x - 1][y] != 6)
	{
		if(office_temp[x-1][y] == 0)
		{
			office_temp[--x][y] = 9;
		}
		else
		{
			x--;
		}
	}
	return office_temp;
}

void dfs(int cnt, int rotate, int office_temp[][9])
{
	int office_next[9][9] = { 0, };
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++) 
		{
			office_next[i][j] = office_temp[i][j];
		}
	}
	if (camera.size() == 0)
	{
		temp = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (office_temp[i][j] == 0)		temp = temp + 1;
			}
		}
		result = min(result, temp);
		return;
	}
	if (cnt > camera.size() - 1)
	{
		temp = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (office_temp[i][j] == 0)		temp = temp + 1;
			}
		}
		result = min(result, temp);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cout << office_temp[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl << result << endl;
		return;
	}

	if (rotate > 3)		return;

	int x = camera_point[cnt].first, y = camera_point[cnt].second;

	if (camera[cnt] == 1)
	{
		// 오른쪽 방향 기준
		if (rotate == 0)		office_temp = right(x, y, office_temp);
		//아래쪽 방향 기준
		else if (rotate == 1)	office_temp = down(x, y, office_temp);
		// 왼쪽 방향 기준
		else if (rotate == 2)	office_temp = left(x, y, office_temp);
		// 위쪽 방향 기준
		else if (rotate == 3)	office_temp = up(x, y, office_temp);
	}
	else if (camera[cnt] == 2)
	{
		// 좌우 방향 기준
		if (rotate == 0 || rotate == 2)
		{
			office_temp = right(x, y, office_temp);
			office_temp = left(x, y, office_temp);
		}
		// 상하 방향 기준
		else if (rotate == 1 || rotate == 3)
		{
			office_temp = down(x, y, office_temp);
			office_temp = up(x, y, office_temp);
		}
	}
	else if (camera[cnt] == 3)
	{
		// 상, 우 방향 기준
		if (rotate == 0)
		{
			office_temp = right(x, y, office_temp);
			office_temp = up(x, y, office_temp);
		}
		// 우, 하 방향 기준
		else if (rotate == 1)
		{
			office_temp = down(x, y, office_temp);
			office_temp = right(x, y, office_temp);
		}
		//하, 좌 방향 기준
		else if (rotate == 2)
		{
			office_temp = down(x, y, office_temp);
			office_temp = left(x, y, office_temp);
		}
		//좌, 상 방향 기준
		else if (rotate == 3)
		{
			office_temp = up(x, y, office_temp);
			office_temp = left(x, y, office_temp);
		}
	}
	else if (camera[cnt] == 4)
	{
		// 상, 우, 하 방향 기준
		if (rotate == 0)
		{
			office_temp = right(x, y, office_temp);
			office_temp = up(x, y, office_temp);
			office_temp = down(x, y, office_temp);
		}
		// 우, 하, 좌 방향 기준
		else if (rotate == 1)
		{
			office_temp = down(x, y, office_temp);
			office_temp = right(x, y, office_temp);
			office_temp = left(x, y, office_temp);
		}
		//하, 좌, 상 방향 기준
		else if (rotate == 2)
		{
			office_temp = down(x, y, office_temp);
			office_temp = left(x, y, office_temp);
			office_temp = up(x, y, office_temp);
		}
		//좌, 상, 우 방향 기준
		else if (rotate == 3)
		{
			office_temp = up(x, y, office_temp);
			office_temp = left(x, y, office_temp);
			office_temp = right(x, y, office_temp);
		}
	}
	else if (camera[cnt] == 5)
	{
		office_temp = up(x, y, office_temp);
		office_temp = left(x, y, office_temp);
		office_temp = right(x, y, office_temp);
		office_temp = down(x, y, office_temp);
	}
	
	dfs(cnt+1, rotate, office_temp);
	dfs(cnt, rotate+1, office_next);
}

int main()
{
	int office[9][9] = { 0, }, next[9][9] = {0,};
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> num;
			office[i][j] = num;
			if (num > 0 && num < 6)
			{
				camera.push_back(num);
				camera_point.push_back(make_pair(i, j));
			}
		}
	}

	dfs(0, 0, office);
	cout << result;
	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾았으나 해결법을 모르겠습니다.

bgjuw12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말