🎲質問する

住所：シラサギ1799

チェスチェスには対角線方向に移動できるビショップがある.ピシャップが図1>に示すような正方形のチェス盤にBと表記された場所がある場合、ピシャップは対角線方向に移動し、Oと表記された格子の他の馬を捕まえることができる.

＜図1＞
しかしチェス盤にはピシャップが置けないところがある.図2>では,チェス盤に色を塗った部分は,ビショップでは置けないと述べている.このようなチェス盤では、双方が互いに相手を捕まえられなければ、「図3」に示すように、最大7つの毕紹普を設置することができる.  色を塗った部分はビザンプを置くことはできませんが、行けます.

＜図2＞

<図3>
正方形のチェス盤の片側の格数をチェス盤の大きさと呼ぶ.チェスの碁盤の大きさと各碁盤の格にビザを置くことができるかどうかについての情報を与えるときは、プログラムを作成して、ビザの最大数を求めてください.そうすれば、ビザは互いにつかめない位置に置くことができます.

入力

1行目はチェス盤の大きさを与える.チェス盤の大きさは10以下の自然数です.2行目から、以下の例に示すように、チェス盤の各マスにビショップを置くことができるかどうかについての情報は、チェス盤単位で1行ずつ与えられる.ビザンプが置ける場所は1、ビザンプが置けない場所は0でスペースを隔てています.

のり付け

解答方法
DFSを利用したバックグラウンドトラッキングの問題です.これはDFSだけでなく,いかに時間を短縮するかを考える必要がある.初期には、簡単に配置できるすべての配列にアクセスしてDFSを迂回することでアクセスしましたが、タイムアウトします.あちこち検索した結果、チェス盤の白と黒のタイルのビショップは衝突しないので、白と黒のタイルの2つに分けてプラスするとN/2の時間短縮効果が見られます.

チェス盤の幅Nを入力し、タイル情報を入力します.

白タイルにビザンプ(v)を置き、黒タイルにビザンプ(v 2)を置き、両方の場合にベクトルを生成し、配置可能な位置に座標をベクトルに入れる.

void init() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			board[i][j] = num;

			if (num == 1) {
				if (((i + j) % 2) == 1) v.push_back({ i, j });
				else v2.push_back({ i, j });
			}
		}
	}
}

v.size()およびv 2.size()はそれぞれdfsを返します.

の各結果を格納して加算すると、結果が出力されます.

void solve() {

	for (int i = 0; i < v.size(); i++) dfs(i, 0, v);
	
	int tmp = result;
	result = 0;
	for (int i = 0; i < v2.size(); i++) dfs(i, 0, v2);

	cout << result + tmp;
}

ベクトルのインデックス値、ベクトル、bishop個数をパラメータとするdfs関数を記述します.

インデックス値がベクトルのサイズと同じである場合(すべての可能な場合に巡回)、巡回時に、ピシャップの個数と既存のピシャップの最大値とを比較することによって、より大きな値が格納される.

インデックスの座標がbishop位置決め可能な座標である場合、dfsを実行するために、インデックスサイズ、bishop個数がボードに表示され、追加される.

はまた、インデックスが最後の値でなくてもdfs関数でループするインデックス値を増加させる.

void dfs(int index, int cnt, vector<pair<int, int>> v ) {

	if (index == v.size()) {
		result = max(cnt,result);
		return;
	}

	int x = v[index].first;
	int y = v[index].second;

	if (chk_bishop(x, y)) {
		board[x][y] = -1;
		dfs(index + 1, cnt + 1, v);
		board[x][y] = 1;
	}

	dfs(index + 1, cnt, v);

	return;
	}

完全なコード

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

using namespace std;

int N, result;
vector<pair<int, int>> v;
vector<pair<int, int>> v2;
int board[10][10] = {0,};
int direction[4][2] = { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };

void init();
void solve();
void dfs(int, int, vector<pair<int, int>>);
bool chk_bishop(int, int);
bool is_inside(int);

void init() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			board[i][j] = num;

			if (num == 1) {
				if (((i + j) % 2) == 1) v.push_back({ i, j });
				else v2.push_back({ i, j });
			}
		}
	}
}

void solve() {

	for (int i = 0; i < v.size(); i++) dfs(i, 0, v);
	
	int tmp = result;
	result = 0;
	for (int i = 0; i < v2.size(); i++) dfs(i, 0, v2);

	cout << result + tmp;
}

void dfs(int index, int cnt, vector<pair<int, int>> v ) {

	if (index == v.size()) {
		result = max(cnt,result);
		return;
	}

	int x = v[index].first;
	int y = v[index].second;

	if (chk_bishop(x, y)) {
		board[x][y] = -1;
		dfs(index + 1, cnt + 1, v);
		board[x][y] = 1;
	}

	dfs(index + 1, cnt, v);

	return;
}

bool chk_bishop(int x, int y) {

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			int tmp = x + (direction[j][0] * i);
			int tmp2 = y + (direction[j][1] * i);
			if (is_inside(tmp) && is_inside(tmp2)) {
				if (board[x + (direction[j][0] * i)][y + (direction[j][1] * i)] == -1)
					return false;
			}
		}
	}
	return true;
}

bool is_inside(int x) {
	return (0 <= x && x < N);
}

int main() {
	init();
	solve();

	return 0;
}