NC24283. [USACO 2018 Ope B]Team Tic Tac Toe
描述
这些奶牛最近沉迷于井字游戏，但是由于她们并不满足只有两头奶牛可以一起玩，她们改编了这个游戏，可以让许多奶牛可以一块儿玩！就像常规的井字游戏一样，这个游戏是在一块3×3的棋盘上进行的，只是与仅用X和O不同，每个格子用一个A…Z之间的字母标记，表示占有这个格子的奶牛名字的首字母。
以下是一个棋盘的例子：
COW XXO ABC
这些奶牛会在她们迷惑于如何判断胜负之前就占满这九个格子。显然，就像常规的井字游戏一样，如果任何一头奶牛占有了一整行、一整列，或是一整条对角线，那么这头奶牛就获胜了。然而，由于奶牛认为多牛游戏中这并不容易出现，所以她们决定允许奶牛组成两牛一队，如果某一行、一列，或是一条对角线仅包含一队的两头奶牛的字母，并且同时包含了这两头奶牛（不仅仅是一头）的字母，那么这一队就获胜。
请帮助奶牛们判断有多少头奶牛或是两头奶牛组成的队伍可以获胜。注意棋盘上的同一个格子可能在不同奶牛或队伍的获胜中均被用到。
输入描述
输入包含三行，每行三个A…Z之间的字符。
输出描述
输出包含两行。第一行，输出能够获胜的单独的奶牛的数量。第二行，输出能够获胜的两头奶牛组成的队伍的数量。
示例1
输入:
COW XXO ABC
输出:
0 2
说明:
在这个例子中，没有单独的奶牛可以获得胜利。但是，如果奶牛C和奶牛X组队，她们可以通过C-X-C对角线获胜。同样地，如果奶牛X和O组队，她们可以通过中间一行取胜。Python3(3.5.2) 解法, 执行用时: 32ms, 内存消耗: 3524K, 提交时间: 2019-06-29 20:27:28
arr=[input() for i in range(3)]
dict01={}
dict02={}
for i in range(3) :
tmp_dict1={}
tmp_dict1[arr[i][0]]=1
tmp_dict1[arr[i][1]]=1
tmp_dict1[arr[i][2]]=1
if len(tmp_dict1)==1 :
dict01[arr[i][0]]=1
elif len(tmp_dict1)==2 :
dict02[str(sorted(list(tmp_dict1)))]=1
tmp_dict2={}
tmp_dict2[arr[0][i]]=1
tmp_dict2[arr[1][i]]=1
tmp_dict2[arr[2][i]]=1
if len(tmp_dict2)==1 :
dict01[arr[0][i]]=1
elif len(tmp_dict2)==2 :
dict02[str(sorted(list(tmp_dict2)))]=1
tmp_dict={}
tmp_dict[arr[0][0]]=1
tmp_dict[arr[1][1]]=1
tmp_dict[arr[2][2]]=1
if len(tmp_dict)==1 :
dict01[arr[0][0]]=1
elif len(tmp_dict)==2 :
dict02[str(sorted(list(tmp_dict)))]=1
tmp_dict={}
tmp_dict[arr[0][2]]=1
tmp_dict[arr[1][1]]=1
tmp_dict[arr[2][0]]=1
if len(tmp_dict)==1 :
dict01[arr[0][0]]=1
elif len(tmp_dict)==2 :
dict02[str(sorted(list(tmp_dict)))]=1
# print(dict01)
# print(dict02)
print(len(dict01))
print(len(dict02))
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-06-29 20:19:16
#include<bits/stdc++.h>
typedef long long LL;
char ipt[10];
int ans[5];
int s[130],t[130][130];
void cnt(int x,int y,int z){
int res=3;
if(ipt[x]==ipt[y]&&ipt[z]==ipt[y]){
int k=ipt[x]-'A';
if(!s[k])s[k]=1,ans[1]++;
return;
}
int k1,k2,flag=false;
if(ipt[x]==ipt[y])
k1=ipt[x]-'A',k2=ipt[z]-'A',flag=true;
if(ipt[x]==ipt[z])
k1=ipt[x]-'A',k2=ipt[y]-'A',flag=true;
if(ipt[z]==ipt[y])
k1=ipt[x]-'A',k2=ipt[z]-'A',flag=true;
if(flag&&!t[k1][k2])t[k1][k2]=t[k2][k1]=1,ans[2]++;
}
int main(){
scanf("%s%s%s",ipt,ipt+3,ipt+6);
cnt(0,1,2);
cnt(3,4,5);
cnt(6,7,8);
cnt(0,3,6);
cnt(1,4,7);
cnt(2,5,8);
cnt(0,4,8);
cnt(2,4,6);
printf("%d\n%d\n",ans[1],ans[2]);
}
C++ 解法, 执行用时: 3ms, 内存消耗: 440K, 提交时间: 2022-05-12 17:02:09
// USACO 2018 Open B. Team Tic Tac Toe
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
const int W = 3;
using IP = pair<int, int>;
vector<string> G(W);
set<set<char>> Win[W + 1];
void insert(const vector<IP>& ps) {
set<char> S;
for (const IP& p : ps) S.insert(G[p.first][p.second]);
Win[S.size()].insert(S);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
_for(r, 0, W) cin >> G[r];
_for(i, 0, W) insert({{i, 0}, {i, 1}, {i, 2}});
_for(i, 0, W) insert({{0, i}, {1, i}, {2, i}});
insert({{0, 0}, {1, 1}, {2, 2}});
insert({{2, 0}, {1, 1}, {0, 2}});
cout << Win[1].size() << endl;
cout << Win[2].size() << endl;
}