#27839 (C++11) No.43 野球の試合

• 問題: No.43 野球の試合
• ユーザー: btk
• 提出日時: 2015-05-21 17:18:05
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,195 bytes
• コンパイル時間: 623 ms
• コンパイル使用メモリ: 64,912 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-06 04:22:27
• 合計ジャッジ時間: 1,239 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	1 ms; 6,944 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	2 ms; 6,944 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	AC	1 ms; 6,940 KB
testcase_10	WA	-

ソースコード

#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++){
		if (judge[0][i] == '-')judge[0][i] = 'o', judge[i][0] = 'x';
	}
	for (int i = 1; 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;
}