QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54526 | #4234. Tic Tac Toe Counting | YL1F4# | WA | 332ms | 4156kb | C++14 | 1.4kb | 2022-10-09 15:31:21 | 2022-10-09 15:31:22 |
Judging History
answer
#include<iostream>
#include<string>
#include<map>
#include<utility>
#include<cstdio>
std::map<std::string,std::pair<int,int>>dp;
char chkwin(std::string s){
if(s[0]==s[1]&&s[1]==s[2]){
return s[0];
}
if(s[3]==s[4]&&s[4]==s[5]){
return s[3];
}
if(s[6]==s[7]&&s[7]==s[8]){
return s[6];
}
if(s[0]==s[3]&&s[3]==s[6]){
return s[0];
}
if(s[1]==s[4]&&s[4]==s[7]){
return s[1];
}
if(s[2]==s[5]&&s[5]==s[8]){
return s[2];
}
if(s[0]==s[4]&&s[4]==s[8]){
return s[0];
}
if(s[2]==s[4]&&s[4]==s[6]){
return s[2];
}
return '.';
}
std::pair<int,int>add(std::pair<int,int>a,std::pair<int,int>b){
return std::make_pair(a.first+b.first,a.second+b.second);
}
std::pair<int,int> dfs(std::string s,char q){
if(dp.count(s)){
return dp[s];
}
// std::cout<<s<<std::endl;
if(chkwin(s)==(q=='X'?'O':'X')){
// std::cout<<":fck"<<" "<<s<<" "<<chkwin(s)<<std::endl;
if(q=='X'){
dp[s]=std::make_pair(1,0);
}else{
dp[s]=std::make_pair(0,1);
}
return dp[s];
}
for(int i=0;i<9;i++){
if(s[i]=='.'){
auto tmp=s;
tmp[i]=q;
dp[s]=add(dp[s],dfs(tmp,(q=='X'?'O':'X')));
}
}
return dp[s];
}
int main(){
dfs(".........",'X');
int T;scanf("%d",&T);
while(T--){
std::string s;
std::cin>>s;
if(!dp.count(s)){
puts("-1 -1");
}else{
printf("%d %d\n",dp[s].second,dp[s].first);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 9ms
memory: 4156kb
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: 332ms
memory: 4100kb
input:
100000 ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......
output:
133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 133128 78408 1...
result:
wrong answer 1st lines differ - expected: '131184 77904', found: '133128 78408'