QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#481701 | #5509. Kooky Tic-Tac-Toe | UESTC_DECAYALI# | WA | 0ms | 3880kb | C++17 | 3.1kb | 2024-07-17 13:24:03 | 2024-07-17 13:24:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int t, n, k;
struct Node{
string tbl[N];
};
using pii = pair<int, int>;
int calc(Node &cur, int r, int c, int dr, int dc){
int res=1;
for (int x=1; x<=n; ++x){
int nr=r+dr*x, nc=c+dc*x;
if (nr<=0 || nr>n || nc<=0 || nc>n) break;
if (cur.tbl[nr][nc]!=cur.tbl[r][c]) break;
++res;
}
return res;
}
pii findChain(Node &cur){
int anso=0, ansx=0;
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; ++j){
if ('.'==cur.tbl[i][j]) continue;
if ('o'==cur.tbl[i][j]){
anso = max(anso, calc(cur, i, j, 0, 1));
anso = max(anso, calc(cur, i, j, 1, 0));
anso = max(anso, calc(cur, i, j, 1, 1));
anso = max(anso, calc(cur, i, j, 1, -1));
}
if ('x'== cur.tbl[i][j]){
ansx = max(ansx, calc(cur, i, j, 0, 1));
ansx = max(ansx, calc(cur, i, j, 1, 0));
ansx = max(ansx, calc(cur, i, j, 1, 1));
ansx = max(ansx, calc(cur, i, j, 1, -1));
}
}
}
return {anso, ansx};
}
void genMove(vector<pii> &res, Node &cur, char ch){
vector<pii> vec1, vec2;
for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j){
if ('.'==cur.tbl[i][j]) continue;
if (ch==cur.tbl[i][j]) vec1.emplace_back(i, j);
else vec2.emplace_back(i, j);
}
res.clear();
for (int i=0; i<(int)vec1.size(); ++i){
res.push_back(vec1[i]);
if (i<vec2.size()) res.push_back(vec2[i]);
}
}
void solve(){
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--){
Node nd;
cin >> n >> k;
// printf("n=%d k=%d\n", n, k);
for (int i=1; i<=n; ++i){
cin >> nd.tbl[i];
nd.tbl[i] = '$' + nd.tbl[i];
}
int cntx=0, cnto=0, cntd=0;
for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j){
if ('o'==nd.tbl[i][j]) ++cnto;
else if ('x'==nd.tbl[i][j]) ++cntx;
else ++cntd;
}
if (abs(cntx-cnto)>1){
cout << "NIE\n";
continue;
}
auto [anso, ansx] = findChain(nd);
bool ok=true;
if (ansx>=k && anso>=k) ok=false;
if (ansx>=2*k || anso>=2*k) ok=false;
if (!ok) cout << "NIE\n";
else{
char winner='.';
if (ansx>=k) winner='x';
if (anso>=k) winner='o';
if ('.'==winner){
if (0==cntd){
vector<pii> res;
genMove(res, nd, (winner=='o' ? 'x' : 'o'));
cout << "TAK\n";
for (auto [x, y] : res){
cout << x << ' ' << y << '\n';
}
}else cout << "NIE\n";
}else if (('o'==winner && cnto<cntx) || ('x'==winner && cntx<cnto)){
cout << "NIE\n";
}else{
ok=false;
int ar, ac;
Node nxt;
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; ++j){
if (winner==nd.tbl[i][j]){
nxt=nd;
nxt.tbl[i][j]='.';
auto [lo, lx] = findChain(nxt);
if (lo<k && lx<k){
ar=i, ac=j;
ok=true; break;
}
}
}
if (ok) break;
}
if (!ok) cout << "NIE\n";
else{
vector<pii> res;
genMove(res, nxt, (winner=='o' ? 'x' : 'o'));
cout << "TAK\n";
for (auto [x, y] : res){
cout << x << ' ' << y << '\n';
}
cout << ar << ' ' << ac << '\n';
}
}
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3880kb
input:
7 3 3 x.o xxx o.o 4 3 xx.x ...o ..o. .o.. 3 3 xoo oxx xoo 3 2 xoo oxx xoo 3 3 xox .o. xox 3 2 xo. ..x xo. 3 3 x.. .x. ..x
output:
TAK 1 3 1 1 3 1 2 2 3 3 2 3 2 1 TAK 1 1 3 3 1 2 4 2 1 4 2 4 TAK 1 2 1 1 1 3 2 2 2 1 2 3 3 2 3 1 3 3 NIE NIE NIE NIE
result:
wrong answer Contestant's solution doesn't alternate between circles and crosses (test case 1)