QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416675 | #4234. Tic Tac Toe Counting | frizzfrizz# | WA | 39ms | 4768kb | C++14 | 3.6kb | 2024-05-22 02:17:33 | 2024-05-22 02:17:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define A first
#define B second
#define SZ(x) (int)(x.size())
#define FR(i, a, b) for (int i = (a); i < (b); i++)
#define FOR(i, n) FR(i, 0, n)
int T;
vector<vector<int> > regs;
unordered_map<string, int> dist, xWin, oWin;
vector<string> ofDist[10];
int status(string b) // assuming a valid board, is it 0 not over, 1 win for X, 2 win for O, 3 tie
{
FOR(ri, SZ(regs))
{
FOR(i, 2)
{
if (b[regs[ri][i]] != b[regs[ri][i + 1]])
break;
if (i == 1 && b[regs[ri][i]] == 'X')
return 1;
if (i == 1 && b[regs[ri][i]] == 'O')
return 2;
}
}
FOR(i, 3)
FOR(j, 3)
if (b[3 * i + j] == '.')
return 0;
return 3;
}
vector<string> get_neis(string b) // assuming correct board state, generate next states
{
int stat = status(b), xCo = 0, oCo = 0;
if (stat != 0)
return {};
vector<int> dotLoc;
vector<string> neis;
FOR(i, 9)
{
if (b[i] == 'X')
xCo++;
if (b[i] == 'O')
oCo++;
if (b[i] == '.')
dotLoc.push_back(i);
}
if (oCo == xCo)
{
FOR(i, SZ(dotLoc))
{
string nex = b;
nex[dotLoc[i]] = 'X';
neis.push_back(nex);
}
return neis;
}
FOR(i, SZ(dotLoc))
{
string nex = b;
nex[dotLoc[i]] = 'O';
neis.push_back(nex);
}
return neis;
}
int main()
{
cin >> T;
FOR(i, 3)
{
vector<int> v;
FOR(j, 3)
v.push_back(3 * i + j);
regs.push_back(v);
}
FOR(j, 3)
{
vector<int> v;
FOR(i, 3)
v.push_back(3 * i + j);
regs.push_back(v);
}
regs.push_back({0, 4, 8});
regs.push_back({2, 4, 6});
queue<string> q;
string st = ".........";
q.push(st);
dist[st] = 0;
while (!q.empty())
{
string cur = q.front();
q.pop();
vector<string> neis = get_neis(cur);
FOR(i, SZ(neis))
{
if (dist.find(neis[i]) == dist.end())
{
dist[neis[i]] = dist[cur] + 1;
ofDist[dist[neis[i]]].push_back(neis[i]);
q.push(neis[i]);
}
}
}
for (int d = 9; d >= 0; d--)
{
FOR(i, SZ(ofDist[d]))
{
int stat = status(ofDist[d][i]);
if (stat == 1)
{
xWin[ofDist[d][i]] = 1;
oWin[ofDist[d][i]] = 0;
continue;
}
if (stat == 2)
{
xWin[ofDist[d][i]] = 0;
oWin[ofDist[d][i]] = 1;
continue;
}
if (stat == 3)
{
xWin[ofDist[d][i]] = 0;
oWin[ofDist[d][i]] = 0;
continue;
}
vector<string> neis = get_neis(ofDist[d][i]);
xWin[ofDist[d][i]] = 0;
oWin[ofDist[d][i]] = 0;
FOR(j, SZ(neis))
{
xWin[ofDist[d][i]] += xWin[neis[j]];
oWin[ofDist[d][i]] += oWin[neis[j]];
}
}
}
while (T--)
{
string s;
cin >> s;
if (xWin.find(s) == xWin.end())
cout << "-1 -1\n";
else
cout << xWin[s] << " " << oWin[s] << "\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 4768kb
input:
4 XX..O.... X...OX... OOOX.X.X. OOOXXX...
output:
191 194 232 200 0 1 -1 -1
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 39ms
memory: 4716kb
input:
100000 ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 1st lines differ - expected: '131184 77904', found: '-1 -1'