글 읽기 - 뭐가 틀린건지... -

us10 2년 전 0

뭐가 틀린건지.. 도무지. 감이..

반례가 있을지요 잠을 못자네요 이거

#include <iostream>

using namespace std;

#define MIN 3
#define MAX 20

int matrix[MAX][MAX];
int virus_matrix[MAX][MAX];
//int visited[MAX][MAX];
int temp_matrix[MAX][MAX];

int N, M;

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

typedef struct _pos {
	int row;
	int col;
} Pos;

int result;
int max_result = -1;

Pos queue[MAX*MAX];
int front, rear;

void Enqueue(Pos p)
{
	queue[front++] = p;
}
Pos Dequeue()
{
	return queue[rear++];
}
bool IsEmptyQueue()
{
	return front == rear;
}

void copy_matrix(int (*src)[MAX], int (*dest)[MAX])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			dest[i][j] = src[i][j];
		}
	}
}

bool IsValid(Pos p)
{
	if ((p.row >= 0 && p.row < N)
		&& (p.col >= 0 && p.col < M)
		&& (virus_matrix[p.row][p.col] == 0)
		)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void BFS()
{
	front = rear = 0;
	result = 0;

	copy_matrix(temp_matrix, virus_matrix);

	Pos p;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (virus_matrix[i][j] == 2)
			{
				p = { i, j };
				Enqueue(p);
			}
		}
	}

	while (!IsEmptyQueue())
	{
		p = Dequeue();
		virus_matrix[p.row][p.col] = 2;

		for (int i = 0; i < 4; i++)
		{
			Pos temp = { p.row + dx[i], p.col + dy[i] };
			if (IsValid(temp))
			{
				//virus_matrix[p.row][p.col] = 2;
				Enqueue(temp);				
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (virus_matrix[i][j] == 0)
			{
				result++;
			}
		}
	}

	if (max_result < result)
	{
		max_result = result;
	}
}

void make_wall(int cnt)
{
	if (cnt == 0)
	{
		BFS();
		return ;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (temp_matrix[i][j] == 0)
			{
				temp_matrix[i][j] = 1;
				make_wall(cnt - 1);
				temp_matrix[i][j] = 0;
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> matrix[i][j];
		}
	}

	copy_matrix(matrix, temp_matrix);

	make_wall(3);

	cout << max_result << "\n";
#if 0
	cout << "\n";
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << temp_matrix[i][j] << " ";
		}
		cout << "\n";
	}
#endif
	system("pause");
	return 0;
}

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

문제

문제

출처

ICPC

뭐가 틀린건지... -_-

us10 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말