글 읽기 - 14502 연구소 문제에서 ..

greeneye 6년 전 0

이 문제에서 다른 분 코드 참고했어요.
왜 dfs() 함수에서 for문을 돌릴때,

i는 x부터 j는 0부터 시작할까요.
둘다 x, y부터 시작해야 할 것 같은데, 제 생각이 왜 틀린지 잘 모르겠어요..

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

#define MAX_SIZE 8

using namespace std;
int map[MAX_SIZE][MAX_SIZE];
int m, n;
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

vector<pair<int, int> > virus;

void input()
{
	scanf("%d %d", &m, &n);
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &map[i][j]);

			if (map[i][j] == 2) virus.push_back(make_pair(i, j));
		}
	}
}

void copy_map(int(*a)[MAX_SIZE], int(*b)[MAX_SIZE])
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			a[i][j] = b[i][j];
		}
	}
}

int recovery(int(*a)[MAX_SIZE], int(*b)[MAX_SIZE])
{
	int ret = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (a[i][j] == 0) ret++;
			a[i][j] = b[i][j];
		}
	}
	return ret;
}

void bfs()
{
	queue<pair<int, int> > q;
	for (int i = 0; i < virus.size(); i++) q.push(virus[i]);

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0)
				continue;

			map[nx][ny] = 2;
			q.push(make_pair(nx, ny));
		}
	}
}

void dfs(int x, int y, int d)
{
	map[x][y] = 1;
	visit[x][y] = 1;

	if (d == 3)
	{
		//bfs
		int tmp[MAX_SIZE][MAX_SIZE];
		copy_map(tmp, map);

		bfs();
		max_value = max(max_value, recovery(map, tmp));

		visit[x][y] = 0;
		map[x][y] = 0;
		return;
	}

	for (int i = x; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visit[i][j] || map[i][j] != 0) continue;
			dfs(i, j, d + 1);
		}
	}

	map[x][y] = 0;
	visit[x][y] = 0;
}

void process()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] != 0) continue;
			dfs(i, j, 1);
		}
	}

	printf("%d\n", max_value);
}

int main()
{
	input();
	process();

	return 0;
}

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

문제

문제

출처

ICPC

14502 연구소 문제에서 ..

greeneye 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말