Tic Tac Toe

Tic Tac Toe

时间: 1ms        内存:128M

描述:

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

提示:

参考答案(内存最优[10060]):

#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[1000][1000];
int fd[1000][1000];
int jd[1000][1000];
void bfs(deque<pair<int,int> > &q, int (*d)[1000]) {
  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");
  }
}

参考答案(时间最优[208]):

#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[2000][2000];
int nmark[2],prev;
bool full;
int nlines[2];
int nkey[2][3000][3000];
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[0];
    else if (grid[i][j] == 'O') ++nmark[1];
    else full = 0;
  }

  if (nmark[0] == nmark[1]) prev = 1;
  else if (nmark[0] == nmark[1]+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]);
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注