QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624576 | #4234. Tic Tac Toe Counting | NYCU_CartesianTree# | WA | 24ms | 5144kb | C++14 | 2.9kb | 2024-10-09 16:09:35 | 2024-10-09 16:09:36 |
Judging History
answer
//============================================================================
// Name : J.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pb push_back
vector<vector<char>> a(4), tot(4);
int num=0, ans1=0, ans2=0;
bool win(){
for(int i=1;i<=3;i++){
set<char>t;
for(int j=1;j<=3;j++) t.insert(a[i][j]);
if(t.size()==1){
if(*t.begin()=='O') return 2;
else if(*t.begin()=='X') return 1;
}
}
for(int i=1;i<=3;i++){
set<char>t;
for(int j=1;j<=3;j++) t.insert(a[j][i]);
if(t.size()==1){
if(*t.begin()=='O') return 2;
else if(*t.begin()=='X') return 1;
}
}
{
set<char>t;
t.insert(a[1][1]);
t.insert(a[2][2]);
t.insert(a[3][3]);
if(t.size()==1){
if(*t.begin()=='O') return 2;
else if(*t.begin()=='X') return 1;
}
}
{
set<char>t;
t.insert(a[1][3]);
t.insert(a[2][2]);
t.insert(a[3][1]);
if(t.size()==1){
if(*t.begin()=='O') return 2;
else if(*t.begin()=='X') return 1;
}
}
return 0;
}
bool ok=0;
map<vector<vector<char> >, pair<int, int> > ans;
void dfs(int t){
if(ans.find(a) != ans.end()){
return;
}
ans[a] = {0, 0};
auto &p = ans[a];
int ww = win();
if(ww){
if(t % 2 == 1){
p.second++;
}else{
p.first++;
}
return;
}
if(t == 10)
return;
// for(int i = 1; i <= 3; i++){
// for(int j = 1; j <= 3; j++){
// cerr << a[i][j];
// }
// cerr << '\n';
// }
char now = (t % 2) ? 'X' : 'O';
for(int i = 1; i <= 3; i++){
for(int j = 1; j <= 3; j++){
if(a[i][j] == '.'){
a[i][j] = now;
dfs(t + 1);
p.first += ans[a].first;
p.second += ans[a].second;
a[i][j] = '.';
}
}
}
}
//
//
//void go(int t){
// if(t-1==num){
// if(!eq()) return;
// ok=1;
// }
//
// int ww=win();
// if(ww){
// if(t-1<num) return;
// if(ww==1) ans1++;
// else ans2++;
// return;
// }
// if(t==10) return;
// char now='O';
// if(t%2) now='X';
// for(int i=1;i<=3;i++){
// for(int j=1;j<=3;j++){
// if(a[i][j]=='.'){
// a[i][j]=now;
// go(t+1);
// a[i][j]='.';
// }
// }
// }
//
//}
void solve(){
string aa;
cin>>aa;
int x=1, y=1;
for(auto t: aa){
tot[x][y]=t;
y++;
if(y == 4){
y = 1;
x++;
}
}
if(ans.find(tot) != ans.end()){
auto &p = ans[tot];
cout << p.first << ' ' << p.second << '\n';
}else{
cout << -1 << '\n';
}
}
signed main() {
ios::sync_with_stdio(0);cin.tie(0);
for(int i=1;i<=3;i++) {
a[i].resize(4);
tot[i].resize(4);
for(int j=1;j<=3;j++) a[i][j]='.';
}
dfs(1);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 24ms
memory: 5144kb
input:
4 XX..O.... X...OX... OOOX.X.X. OOOXXX...
output:
191 194 232 200 0 1 -1
result:
wrong answer 4th lines differ - expected: '-1 -1', found: '-1'