白駿16988

質問リンク

https://www.acmicpc.net/problem/16988

質問する

に答える

すべての状況の数を考慮してbfsを返して解放する.
大きな仕事をするには以下の2種類があります.

私の石を置く2つの位置を見つけて、石を置いてみます

backtrackingアルゴリズムとnext permutationアルゴリズムを使用して、配置する2つの場所を選択できます.

次のコードはnext置換を使用しています.

今の碁盤からどれだけの石が得られるか数えてみましょう.

1番に石を置く場合,現在盤の状態で取れる石がいくつあるかについてcountを行った.

カウントダウンの方法は地図を巡り、敵の石であればキューに入れてbfsに戻ります.

bfsを回転中に敵の石に隣接する空白空間(0)がある場合は、0を返します.

そうでなければ三俊石の個数が返されます.

コード#コード#

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct {
	int x;
	int y;
}pos;
int n, m, ans;
int maps[21][21];
bool vi[21][21];
queue<pos> q;

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

int bfs(int x, int y, int type) {

	int cnt = 1;
	int check = 1;
	q.push({ x,y });
	vi[x][y] = true;

	while (!q.empty()) {
		int nowx = q.front().x;
		int nowy = q.front().y;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextx = nowx + dx[i];
			int nexty = nowy + dy[i];

			if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
			if (!vi[nextx][nexty]) {
				if (maps[nextx][nexty] == 0) check = 0;
				else if (maps[nextx][nexty] == type) {
					q.push({ nextx,nexty });
					vi[nextx][nexty] = true;
					cnt++;
				}
			}
		}
	}

	if (check) return cnt;
	else return 0;

}

int simulation() {
	fill(&vi[0][0], &vi[20][21], false);

	int total_cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] == 2 && !vi[i][j]) {
				total_cnt += bfs(i, j, maps[i][j]);
			}
		}
	}

	return total_cnt;
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maps[i][j];
		}
	}


	vector<int> sel;
	for (int i = 0; i < n * m - 2; i++) sel.push_back(0);
	for (int i = 0; i < 2; i++) sel.push_back(1);

	do {
		vector<pos> selected;
		for (int i = 0; i < sel.size(); i++) {
			if (sel[i] == 1) {
				int x = i / m;
				int y = i % m;
				if (maps[x][y] == 0) selected.push_back({ x,y });
			}
		}

		if (selected.size() == 2) {
			for (int i = 0; i < 2; i++) maps[selected[i].x][selected[i].y] = 1;
			ans = max(ans, simulation());
			for (int i = 0; i < 2; i++) maps[selected[i].x][selected[i].y] = 0;
		}

	} while (next_permutation(sel.begin(), sel.end()));

	cout << ans;

}

ポスト

おなじみのタイプなので、早く解きたいのでコードが乱れているような気がします.