思路
【非常暴力的做法】遍历每一行、每一列、每一条对角线,将对应牛出现的频次存储在 $26$ 个字母的哈希表中。每次存储完,遍历字母表,如果有 $3$ 次的那就标记一头牛可获胜,如果有同一列只有两头牛就标记为可胜策略,按字典序放入pair
,存入set
中,防止重复【见测试数据 $10$ 】。
需要注意的是两头牛获胜的情况不需要标记,因为同样的一头牛可以跟另一头搭配获胜;但一头牛就可以获胜的需要标记,假如某两行、两列或是两个对角线都有三头一样的牛可以避免重复计算【见测试数据 $7$ 】对没错我就是没想明白在这几个地方WA了。相当于用set
判两头牛的重,用st
数组判一头牛的重。
存储
用pair
存两头牛可以获胜的情况,放在set
里
用st
数组标记一头牛就可以获胜的情况,最后输出win1
即可
代码实现
#include <bits/stdc++.h>
using namespace std;
char a[3][3];
int b[27], st[27];
set<pair<int, int>> s;
int win1, win2;
int main()
{
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
cin >> a[i][j];
for(int i = 0; i < 3; i++)
{
memset(b, 0, sizeof b);
for(int j = 0; j < 3; j++) b[a[i][j] - 'A']++;
vector<int> V;
for(int i = 0; i < 26; i++)
{
if(b[i]) V.push_back(i);
if(b[i] == 3 && !st[i]) win1++, st[i] = 1;
}
if(V.size() == 2) s.insert(make_pair(V.back(), V.front()));
}
for(int i = 0; i < 3; i++)
{
memset(b, 0, sizeof b);
for(int j = 0; j < 3; j++) b[a[j][i] - 'A']++;
vector<int> V;
for(int i = 0; i < 26; i++)
{
if(b[i]) V.push_back(i);
if(b[i] == 3 && !st[i]) win1++, st[i] = 1;
}
if(V.size() == 2) s.insert(make_pair(V.back(), V.front()));
}
memset(b, 0, sizeof b);
for(int i = 0; i < 3; i++) b[a[i][i] - 'A']++;
vector<int> V;
for(int i = 0; i < 26; i++)
{
if(b[i]) V.push_back(i);
if(b[i] == 3 && !st[i]) win1++, st[i] = 1;
}
if(V.size() == 2) s.insert(make_pair(V.back(), V.front()));
memset(b, 0, sizeof b);
V.clear();
for(int i = 0; i < 3; i++) b[a[i][2 - i] - 'A']++;
for(int i = 0; i < 26; i++)
{
if(b[i]) V.push_back(i);
if(b[i] == 3 && !st[i]) win1++, st[i] = 1;
}
if(V.size() == 2) s.insert(make_pair(V.back(), V.front()));
cout << win1 << endl << s.size();
return 0;
}