[白駿C++14502研究所

質問する

人体致命ウイルスを研究する研究所がウイルスを漏らした.幸いにもウイルスはまだ拡散していないので、ウイルスの拡散を防ぐために、研究所に壁を建てたいと思っています.
研究所の大きさはN×Mの矩形として表すことができ、矩形は1である.×1サイズの正方形に分割します.研究所は1つのスペース、1つの壁で構成され、壁は1つのスペースでいっぱいです.
一部の格子にはウイルスが存在し、このウイルスは上下左右に隣接する格子に伝播することができる.新しく立てた壁は3つあるので,3つ立てなければならない.
たとえば、研究所がある場合を見てみましょう.
このとき、0はスペース、1は壁、2はウイルスがいる場所です.壁を立てなければ、ウイルスはすべてのスペースに拡散することができます.
2行1列、1行2列、4行6列に壁を設けると、地図の形は以下のようになります.
ウイルスが拡散した様子は以下の通り.

3つの壁を設置した後、ウイルスが拡散できない場所を安全区域と呼ぶ.上の地図では、安全区域の大きさは27です.
研究所地図が与えられたタイミングで得られる安全領域の大きさの最値を求めるプログラムを作成した.

入力

第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
2行目からN行目に地図の形状を与える.0はスペース、1は壁、2はウイルスの位置です.2の個数は2以上、10以下の自然数である.
スペースの数は3つ以上です.

しゅつりょく

最初の行で取得できるセキュリティ領域の最大サイズを出力します.
https://www.acmicpc.net/problem/14502

に答える

すべての空きスペースから3つを選択し、壁を立てます...次にウイルスをBFSに変換した後,残存空間(安全空間)の大きさの最値を求める.
最大8個のx 8=64個のスペースのうち、少なくとも63個のスペースがあります.
63_C_3 = 39711... 4万くらいになったので、時間が経つのが早いかと思いきや、
提出すればいいです.
最も重要なnumでは,X順序X cnt個を繰り返す関数を以下に示す.

関数の主体は

void selectWallLoc(int num, vector<int>& selected, int cnt) {
	if (cnt == 0) {
		// to-do-list
		return;
	}
	int cursor = selected.empty() ? 0 : selected.back() + 1;
	for (int i = cursor; i < num; i++) {
		selected.push_back(i); 
		selectWallLoc(num, selected, cnt - 1);
		selected.pop_back(); 
	}
}

こんなに長いです.空きスペースの総数(num)から再帰的に3つ抽出し,抽出後に次の2つの関数を呼び出す.

地図が初めて入力された研究所の様子であれば、最終的に選ばれた3つの数字は、
いずれも空白ベクトル(空白空間の座標を覚える)のインデックスとなり、壁を洗って戻る操作を繰り返します.
最後に,BFSによりウイルスが拡散し,残りの空き領域の数の関数を返す.

セキュリティ領域サイズresは、空白領域−1が通過するたびにコードである.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::pair; using std::queue;
typedef pair<int, int> pii;
/*
map : 초기입력값
virusMap : 임의의 위치에 벽3개를 세운뒤의 맵
visited : BFS에서 중복방문을 막기위한 방문체크용 배열
virus : 바이러스(좌표) 리스트
black : 빈공간(좌표) 리스트
loc : BFS에서 사용할 큐
safetyArea : BFS이후 구해진 안전영역크기의 최댓값
*/
int n, m, **map, safetyArea=0;
int** visited;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
vector<pii> virus, blank;
queue<pii> loc;
void init();
int virusSpread();
void clear();
void resetVirusMap(int a, int b, int c);
void replaceMap(int a, int b, int c);
void selectWallLoc(int num, vector<int>& selected, int cnt);
void func();

void func() {
	vector<int> selected;
	int size = blank.size();
	selectWallLoc(size, selected, 3); //빈공간중 3개를 선택하는 경우를 고름.

	printf("%d", safetyArea); //안전영역 최대크기 출력
}

void selectWallLoc(int num, vector<int>& selected, int cnt) {
	if (cnt == 0) { //3개를 선택한뒤에
		//바이러스맵을만듬
		replaceMap(selected[0], selected[1], selected[2]);
		//만든맵으로 바이러스를 퍼트려봄
		int res = virusSpread();
		if (safetyArea < res) safetyArea = res; 
		//바이러스맵을 초기화
		resetVirusMap(selected[0], selected[1], selected[2]);
		return;
	}
	int cursor = selected.empty() ? 0 : selected.back() + 1;
	for (int i = cursor; i < num; i++) {
		selected.push_back(i); //선택한목록에 넣음
		selectWallLoc(num, selected, cnt - 1); //재귀적으로 cnt개를 선택
		selected.pop_back(); //선택한요소를 뺌
	}
}

void replaceMap(int a, int b, int c) { //빈공간a,b,c에 벽을세움
	map[blank[a].first][blank[a].second] = 1; 
	map[blank[b].first][blank[b].second] = 1;
	map[blank[c].first][blank[c].second] = 1;
}

void resetVirusMap(int a, int b, int c) {//a,b,c에 벽을허물고 빈공간으로
	map[blank[a].first][blank[a].second] = 0;
	map[blank[b].first][blank[b].second] = 0;
	map[blank[c].first][blank[c].second] = 0;
}

//방문 배열 초기화
void clear() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visited[i][j] = false;

}

//바이러스를 퍼트리고 남은 안전영역크기를 리턴함
int virusSpread() {
	clear();
	int res = blank.size() - 3; //안전영역 크기 : 벽을3개더세웠으므로 -3
	//처음 바이러스위치를 한번에 큐에 넣고 BFS진행
	for (int k = 0; k < virus.size(); k++) {
		int start_x = virus[k].first;
		int start_y = virus[k].second;
		loc.push({ start_x, start_y });
		visited[start_x][start_y] = true;
	}
	//BFS
	while (!loc.empty()) {
		int x = loc.front().first;
		int y = loc.front().second;
		loc.pop();

		for (int dir = 0; dir < 4; dir++) {
			int xx = x + dx[dir];
			int yy = y + dy[dir];

			if (xx < 0 || yy < 0 || xx == n || yy == m) continue; //맵을벗어나면 제외
			if (map[xx][yy] == 1 || map[xx][yy] == 2) continue; //벽, 바이러스를 만나면 제외
			if (!visited[xx][yy]) { //빈공간이고 처음 방문한곳이면 안전영역크기 -1
				visited[xx][yy] = true;
				res--;
				loc.push({ xx, yy }); //이어서 탐색
			}
		}
	}

	return res;
}

void init() {
	scanf("%d%d", &n, &m);
	map = new int* [n];
	visited = new int* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		visited[i] = new int[m];
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) //바이러스 위치 기록
				virus.push_back({ i, j });
			if (map[i][j] == 0) //빈공간 위치 기록
				blank.push_back({ i, j });
		}
	}
}

int main(void) {
	init();
	func();

	return 0;
}