QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#481701#5509. Kooky Tic-Tac-ToeUESTC_DECAYALI#WA 0ms3880kbC++173.1kb2024-07-17 13:24:032024-07-17 13:24:03

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 13:24:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2024-07-17 13:24:03]
  • 提交

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)