結果

問題 No.43 野球の試合
コンテスト
ユーザー btk
提出日時 2015-05-21 17:18:58
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 1,100 bytes
コンパイル時間 554 ms
コンパイル使用メモリ 65,280 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 04:22:32
合計ジャッジ時間 1,137 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<vector>
#define LL long long
using namespace std;


typedef pair<int, int> P;

int res = 6;
int cnt[6];
string judge[6];
int N,M;

vector<P> ch;
void calc(){
	for (int i = 0; i < N; i++){
		cnt[i] = 0;
		for (int j = 0; j < N; j++){
			if (judge[i][j] == 'o')cnt[i]++;
		}
	}
	int k = 1;
	for (int i = N - 1; i >= 0; i--){
		bool f = false;
		for (int j = 0; j < 6; j++){
			if (cnt[j] == i)
				f = true;
		}
		if (cnt[0] == i)
			res = min(res, k);
		if (f)k++;
	}
}

void backtrack(int n){
	if (n == M){
		calc();
	}
	else{
		judge[ch[n].first][ch[n].second] = 'o';
		judge[ch[n].second][ch[n].first] = 'x';
		backtrack(n + 1);
		judge[ch[n].first][ch[n].second] = 'x';
		judge[ch[n].second][ch[n].first] = 'o';
		backtrack(n + 1);
	}

}

int main(){
	cin >> N;
	res = N;
	for (int i = 0; i < N; i++){
		cin >> judge[i];
		
	}

	for (int i = 0; i < N; i++){
		for (int j = i+1; j < N; j++){
			if (judge[i][j] == '-')ch.push_back(make_pair(i, j));
		}
	}
	M = (int)ch.size();
	backtrack(0);
	cout << res << endl;
}
0