# Tic Tac Toe

Tic Tac Toe The game of Tic Tac Toe is played on an

n

-by-

n

grid (where

n

is usually but not necessarily three). Two players alternate placing symbols on squares of the grid. One player places Xes and the other player places Os. The player placing Xes always goes first. When the grid contains a vertical, horizontal, or diagonal sequence of at least

m

consecutive squares all containing the same symbol, the game ends and the winner is the player who placed the last symbol. When all the squares of the grid are filled, if neither player has won, the game ends in a draw.

Your task is to analyze the state of a Tic Tac Toe board, and determine whether the game is still in progress, or if it has completed, who won, or if the game ended in a draw. You should also detect erroneous states of the Tic Tac Toe board that could never occur during an actual game.

The first line of input contains the two integers n and m, separated by spaces, with 1 <= m <= n <= 2000. The following n lines of input each contain one row of the Tic Tac Toe board. Each of these lines contains exactly n characters, and each of these characters is either an X, an O, or a period (.), indicating an empty square.

Output a single line containing the appropriate string X WINS, O WINS, or DRAW if the game is over, the string IN PROGRESS if the game has not yet finished, or ERROR if the state of the board could never occur during a game.

``````3 3
..X
OOX
..X
``````

``````X WINS
``````

``````#include <cstring>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using namespace std;

#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FORALL(i,v) for(typeof((v).end())i=(v).begin();i!=(v).end();++i)
#define CLR(x,a) memset(x,a,sizeof(x))
#define BEND(v) (v).begin(),(v).end()
#define MP make_pair
#define PB push_back
#define A first
#define B second
#define dump(x) cerr << #x << " = " << (x) << endl
typedef long long ll; typedef long double ld;

const int inf = 0x20202020;

int dr[] = { 0, 1, 0, -1 },
dc[] = { 1, 0, -1, 0 };

int R,C;
char grid;
int fd;
int jd;
void bfs(deque<pair<int,int> > &q, int (*d)) {
while (q.size()) {
int r = q.front().A, c = q.front().B;
q.pop_front();

FOR(k,4) {
int r2 = r+dr[k], c2 = c+dc[k];
if (r2<0 || r2>=R || c2<0 || c2>=C) continue;
if (grid[r2][c2] == '#') continue;

if (1+d[r][c] < d[r2][c2]) {
d[r2][c2] = 1+d[r][c];
q.PB(MP(r2,c2));
}
}
}
}

int main() {
scanf("%d%d",&R,&C);
assert(1 <= R && R <= 1000);
assert(1 <= C && C <= 1000);

deque<pair<int,int> > fq,jq;
CLR(fd,0x20);
CLR(jd,0x20);
FOR(r,R) {
FOR(c,C) {
char ch;
scanf(" %c",&ch);

grid[r][c] = ch;
if (ch=='J') {
jq.PB(MP(r,c));
jd[r][c] = 0;
} else if (ch=='F') {
fq.PB(MP(r,c));
fd[r][c] = 0;
}
}
}
assert(jq.size() == 1);

bfs(fq,fd);
bfs(jq,jd);

int best = inf;
#define TRYIT(r,c) if (grid[r][c] != '#' && jd[r][c] < fd[r][c]) if(best>jd[r][c]+1) best = jd[r][c]+1
FOR(r,R) {
TRYIT(r,0);
TRYIT(r,C-1);
}
FOR(c,C) {
TRYIT(0,c);
TRYIT(R-1,c);
}

if (best < inf) {
printf("%d\n",best);
} else {
printf("IMPOSSIBLE\n");
}
}
``````

``````#include <cstring>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using namespace std;

#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FORI(i,v) FOR(i,(int)(v).size())
#define FORALL(i,v) for(typeof((v).end())i=(v).begin();i!=(v).end();++i)
#define CLR(x,a) memset(x,a,sizeof(x))
#define BEND(v) (v).begin(),(v).end()
#define SZ(v) (int)(v).size()
#define MP make_pair
#define PB push_back
#define A first
#define B second
#define dump(x) cerr << #x << " = " << (x) << endl
typedef long long ll; typedef long double ld;

int n,m;
char grid;
int nmark,prev;
bool full;
int nlines;
int nkey;
int dr[] = { 1, 1, 0, -1 },
dc[] = { 0, 1, 1, 1 };
char get(int r, int c) {
if (r<0 || r>=n || c<0 || c>=n) return '.';
return grid[r][c];
}
void detect(int p, char ch) {
FOR(k,4) {
FOR(r,n) FOR(c,n) {
if (get(r-dr[k],c-dc[k]) != ch) {
int len=0;
while (get(r+len*dr[k],c+len*dc[k]) == ch) ++len;

if (len >= m) {
++nlines[p];

FOR(i,len) if (i<m && m+i >= len) {
++nkey[p][r+i*dr[k]][c+i*dc[k]];
}
}
}
}
}
}
int main() {
scanf("%d%d",&n,&m);

FOR(i,n) FOR(j,n) scanf(" %c",&grid[i][j]);

CLR(nmark,0);
full = 1;

FOR(i,n) FOR(j,n) {
if (grid[i][j] == 'X') ++nmark;
else if (grid[i][j] == 'O') ++nmark;
else full = 0;
}

if (nmark == nmark) prev = 1;
else if (nmark == nmark+1) prev = 0;
else {
printf("ERROR\n");
return 0;
}

CLR(nlines,0);
CLR(nkey,0);
FOR(p,2) {
detect(p,"XO"[p]);
}

if (nlines[1-prev] != 0) {
printf("ERROR\n");
return 0;
}

if (nlines[prev] == 0) {
if (full) printf("DRAW\n");
else printf("IN PROGRESS\n");
return 0;
}

bool happy = 0;
FOR(i,n) FOR(j,n) if (nkey[prev][i][j] == nlines[prev]) happy = 1;

if (!happy) {
printf("ERROR\n");
return 0;
}

printf("%c WINS\n", "XO"[prev]);
}
``````