QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105447 | #5509. Kooky Tic-Tac-Toe | El_Medonho | AC ✓ | 23ms | 3456kb | C++14 | 7.3kb | 2023-05-14 04:25:50 | 2023-05-14 04:25:53 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define mxn 1e5+5
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define endl '\n'
#define pii pair<int,int>
typedef long long ll;
int solve(){
int n,k; cin >> n >> k;
vector<string> gg(n);
vector<vector<char>> grid(n, vector<char> (n));
for(string &s: gg) cin >> s;
int cc1 = 0,cc2 = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
grid[i][j] = gg[i][j];
if(grid[i][j] == 'x') cc1++;
else if(grid[i][j] == 'o') cc2++;
}
}
if(abs(cc1-cc2) > 1){
cout << "NIE\n";
return 0;
}
pii a1 = {-1,-1}, a2 = {-1,-1};
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// bool pj = false;
if(i + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j] != 'x') pass = false;
}
if(pass) a1 = {i,j};
}
if(j + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i][j+g] != 'x') pass = false;
}
if(pass) a1 = {i,j};
}
if(i + k <= n && j + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j+g] != 'x') pass = false;
}
if(pass) a1 = {i,j};
}
if(i + k <= n && j - k >= -1){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j-g] != 'x') pass = false;
}
if(pass) a1 = {i,j};
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// bool pj = false;
if(i + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j] != 'o') pass = false;
}
if(pass) a2 = {i,j};
}
if(j + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i][j+g] != 'o') pass = false;
}
if(pass) a2 = {i,j};
}
if(i + k <= n && j + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j+g] != 'o') pass = false;
}
if(pass) a2 = {i,j};
}
if(i + k <= n && j - k >= -1){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j-g] != 'o') pass = false;
}
if(pass) a2 = {i,j};
}
}
}
if((a1.first != -1 && a2.first != -1) || (a1.first == -1 && a2.first == -1 && cc1+cc2 != n*n) ){
cout << "NIE\n";
return 0;
}
if(a1.first == -1 && a2.first == -1){
cout << "TAK\n";
bool cross = (cc2 > cc1) ? false : true;
bool doo = true;
while(doo){
doo = false;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(cross && grid[i][j] == 'x'){
cout << i+1 << ' ' << j+1 << endl;
cross = false;
grid[i][j] = '.';
doo = true;
}
if(!cross && grid[i][j] == 'o'){
cout << i+1 << ' ' << j+1 << endl;
cross = true;
grid[i][j] = '.';
doo = true;
}
}
}
}
return 0;
}
char w = '.';
pii am;
if(a1.first != -1){
am = a1;
w = 'x';
}else {
am = a2;
w = 'o';
}
am = {-1,-1};
for(int ii = 0; ii < n; ii++){
for(int jj = 0; jj < n; jj++){
if(grid[ii][jj] != w) continue;
bool aa = false;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// bool pj = false;
if(i + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j] != w) pass = false;
if(i+g == ii && j == jj) pass = false;
}
if(pass) aa = true;
}
if(j + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i][j+g] != w) pass = false;
if(i == ii && j+g == jj) pass = false;
}
if(pass) aa = true;
}
if(i + k <= n && j + k <= n){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j+g] != w) pass = false;
if(i+g == ii && j+g == jj) pass = false;
}
if(pass) aa = true;
}
if(i + k <= n && j - k >= -1){
bool pass = true;
for(int g = 0; g < k; g++){
if(grid[i+g][j-g] != w) pass = false;
if(i+g == ii && j-g == jj) pass = false;
}
if(pass) aa = true;
}
}
}
if(aa){
continue;
}
if(!aa){
am = {ii,jj};
}
}
}
if(am.first == -1){
cout << "NIE\n";
return 0;
}
if((w == 'x' && cc1 < cc2) || (w == 'o' && cc2 < cc1)){
cout << "NIE\n";
return 0;
}
grid[am.first][am.second] = '.';
cout << "TAK\n";
vector<pair<int,int>> ans(0);
bool cross = (w == 'x') ? false : true;
bool doo = true;
while(doo){
doo = false;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(cross && grid[i][j] == 'x'){
ans.push_back(make_pair(i, j));
cross = false;
grid[i][j] = '.';
doo = true;
}
if(!cross && grid[i][j] == 'o'){
ans.push_back(make_pair(i, j));
cross = true;
grid[i][j] = '.';
doo = true;
}
}
}
}
reverse(ans.begin(), ans.end());
ans.push_back(am);
for(int i = 0; i < (int) ans.size(); i++){
cout << ans[i].first+1 << ' ' << ans[i].second+1 << endl;
}
return 0;
}
int main(){
fastio;
int t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3452kb
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 2 2 3 3 1 1 3 1 2 1 1 3 2 3 TAK 1 4 3 3 1 2 2 4 1 1 4 2 TAK 1 2 2 2 3 2 1 1 1 3 2 3 3 3 3 1 2 1 NIE NIE NIE NIE
result:
ok correct (7 test cases)
Test #2:
score: 0
Accepted
time: 12ms
memory: 3456kb
input:
10000 3 3 x.o xxx o.o 3 3 xoo oxx xoo 3 2 xoo oxx xoo 3 3 xox .o. xox 3 2 xo. ..x xo. 3 2 oox .xo o.x 5 5 xxx.. xxo.x xoo.. xxxox .oooo 3 3 xxx .o. oo. 3 2 x.o xo. ..o 3 2 ..x xxo .o. 3 3 xxo o.. oxo 3 2 oox ..x ... 3 3 xxo ... .ox 3 3 .xo ... oox 3 3 .x. xo. o.o 3 2 o.. xxo .ox 3 2 x.x xoo x.o 3 2 ...
output:
TAK 2 2 3 3 1 1 3 1 2 1 1 3 2 3 TAK 1 2 2 2 3 2 1 1 1 3 2 3 3 3 3 1 2 1 NIE NIE NIE NIE NIE TAK 3 2 1 2 3 1 1 1 2 2 1 3 NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK 3 2 1 1 3 1 4 2 2 4 2 2 1 3 4 1 2 3 1 4 1 2 4 3 NIE NIE NIE NIE NIE TAK 4 1 1 4 3 4 1 3 3 1 4 3 2 4 1 1 4 4 4 2 ...
result:
ok correct (10000 test cases)
Test #3:
score: 0
Accepted
time: 23ms
memory: 3440kb
input:
10000 6 4 x.xx.o xo.o.x ooox.o o..xo. ..xxxo o.oxx. 6 5 oooxxx oxoxxo xoooxo xoxxxx xooxox xoxxxx 6 3 o.x.x. oo.o.x xx.oo. .x.xx. ooxo.. .xxo.. 6 6 xoo..o o.xx.x oooooo xx.x.. o..xx. ...xxx 6 5 xooxoo ooxxoo xxooxx oxooxx oxoxxx xxoxoo 6 5 xoxxxo ooooxo ooxoxx oxxoox xxxxox ooooxo 6 5 o....o .ox.oo ...
output:
TAK 4 1 1 4 3 3 1 3 6 3 5 5 3 2 1 1 6 1 5 4 2 4 6 5 5 6 5 3 4 5 4 4 3 6 3 4 3 1 2 6 2 2 2 1 1 6 6 4 NIE TAK 4 5 5 4 3 2 2 4 6 3 5 2 4 4 3 5 3 1 2 2 1 5 6 4 6 2 5 1 4 2 3 4 2 6 2 1 1 3 1 1 5 3 NIE TAK 1 1 1 2 1 4 1 5 2 3 2 5 3 1 3 3 3 5 4 1 4 2 4 3 4 5 5 1 5 2 5 3 5 4 6 3 6 4 6 5 2 4 2 6 3 2 3 4 3 6 ...
result:
ok correct (10000 test cases)