如何找到一个任意大小的井字棋游戏中的赢家？ [英] How to find the winner of a tic-tac-toe game of any size?

问题描述

这是一个<一个href="http://www.glassdoor.com/Interview/How-would-you-determine-if-someone-has-won-a-game-of-tic-tac-toe-on-a-board-of-any-size-QTN_1104.htm">interview问题。 你会如何确定是否有人已经赢得了比赛井字棋对任何大小的板？我听到了算法复杂度为O（1）。是否有意义 ？任何人都可以解释的算法？

This is an interview question. "How would you determine if someone has won a game of tic-tac-toe on a board of any size?" I heard the algorithm complexity was O(1). Does it make sense ? Can anybody explain the algorithm ?

推荐答案

答案是正确的页面上，但我无论如何解释。

The answer is right on that page, but I'll explain it anyway.

该算法的复杂度为O（1）确定一个给定的举动将赢得比赛。它不可能是O（1）一般，因为你需要知道该板的状态，以确定一个胜利者。但是，您可以建立一个国家逐步这样你可以决定是否移动胜在O（1）。

The algorithm's complexity is O(1) for determining if a given move will win the game. It cannot be O(1) in general since you need to know the state of the board to determine a winner. However, you can build that state incrementally such that you can determine whether a move wins in O(1).

要开始，有号码为每一行，列和对角线为每个玩家的阵列。在每次移动，增加相应的播放器的行，列和对角线（此举不一定是对角），通过这一举动影响的元素。如果该玩家的数量等于电路板的尺寸，该玩家获胜。

To start, have an array of numbers for each row, column, and diagonal for each player. On each move, increment the elements corresponding to the player for the row, column, and diagonal (the move may not necessarily be on a diagonal) influenced by that move. If the count for that player is equal to the dimension of the board, that player wins.

这篇关于如何找到一个任意大小的井字棋游戏中的赢家？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！