글 읽기 - 1799비숍 그리디로 풀었는데 대부분 되는것같은데 반례좀 들어주세요

rhkd2612 6년 전 0

제가 그리디로 풀었는데 얼추 다 되는거같은데 반례를 모르겠습니다

#include <iostream>
#include <queue>

using namespace std;

#define MAX 12

int sz, answer;

int arr[MAX][MAX];
int temp[MAX][MAX];
int result[MAX][MAX];

struct forQ
{
	forQ(int a, int b, int c)
	{
		x = a;
		y = b;
		weight = c;
	}
	int x;
	int y;
	int weight;
};

bool operator<(const forQ & a, const forQ & b)
{
	if (a.weight == b.weight)
	{
		if (a.y == b.y)
			return a.x > b.x;
		return a.y > b.y;
	}
	return a.weight < b.weight;
}

priority_queue<forQ> q;

int dy[4] = { -1,-1,1,1 };
int dx[4] = { -1,1,-1,1 };

bool Safe(int y, int x)
{
	return y > 0 && x > 0 && y <= sz && x <= sz;
}

void dfs(int y, int x, pair<int,int> direct,bool sDfs)
{
	if (!Safe(y, x))
		return;

	if (direct.first == 0)
	{
		if (sDfs)
			answer++;

		for (int i = 0; i < 4; i++)
			dfs(y + dy[i], x + dx[i], make_pair(dy[i], dx[i]),sDfs);

		for (int i = 1; i <= sz; i++)
		{
			for (int j = 1; j <= sz; j++)
			{
				if (arr[i][j] == 1)
					result[i][j] += 1;

				if(!sDfs)
					arr[i][j] = temp[i][j];
			}
		}
	}
	else
	{
		arr[y][x] = 0;
		dfs(y + direct.first, x + direct.second, direct,sDfs);
	}
}

int main()
{
	cin >> sz;

	for (int i = 1; i <= sz; i++)
	{
		for (int j = 1; j <= sz; j++)
		{
			cin >> arr[i][j];

			temp[i][j] = arr[i][j];
		}
	}

	for (int i = 1; i <= sz; i++)
	{
		for (int j = 1; j <= sz; j++)
		{
			if (arr[i][j] == 1)
				dfs(i, j,make_pair(0,0),false);
		}
	}

	for (int i = 1; i <= sz; i++)
	{
		for (int j = 1; j <= sz; j++)
		{
			if(result[i][j] != 0)
				q.push(forQ(j, i, result[i][j]));
		}
	}

	while (!q.empty())
	{
		forQ t = q.top(); q.pop();

		if (arr[t.y][t.x] == 0)
			continue;

		dfs(t.y, t.x, make_pair(0, 0), true);
	}

	cout << answer << endl;

	return 0;
}

doju 6년 전 0

그리디로 푸는 문제가 아닙니다.

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

문제

문제

출처

ICPC

1799비숍 그리디로 풀었는데 대부분 되는것같은데 반례좀 들어주세요

rhkd2612 6년 전 0

doju 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말