{"id":5904,"date":"2019-12-01T22:51:54","date_gmt":"2019-12-02T06:51:54","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5904"},"modified":"2019-12-01T22:52:17","modified_gmt":"2019-12-02T06:52:17","slug":"leetcode-1275-find-winner-on-a-tic-tac-toe-game","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1275-find-winner-on-a-tic-tac-toe-game\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1275. Find Winner on a Tic Tac Toe Game"},"content":{"rendered":"\n<p>Tic-tac-toe is played&nbsp;by&nbsp;two players&nbsp;<em>A<\/em>&nbsp;and&nbsp;<em>B<\/em>&nbsp;on a&nbsp;<em>3<\/em>&nbsp;x&nbsp;<em>3<\/em>&nbsp;grid.<\/p>\n\n\n\n<p>Here are the rules of Tic-Tac-Toe:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Players take turns placing characters into empty squares (&#8221; &#8220;).<\/li><li>The first player&nbsp;<em>A<\/em>&nbsp;always places &#8220;X&#8221; characters, while the second player&nbsp;<em>B<\/em>&nbsp;always places &#8220;O&#8221; characters.<\/li><li>&#8220;X&#8221; and &#8220;O&#8221; characters are always placed into empty squares, never on filled ones.<\/li><li>The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.<\/li><li>The game also ends if all squares are non-empty.<\/li><li>No more moves can be played if the game is over.<\/li><\/ul>\n\n\n\n<p>Given an array&nbsp;<code>moves<\/code>&nbsp;where each element&nbsp;is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which&nbsp;<em>A<\/em>&nbsp;and&nbsp;<em>B<\/em>&nbsp;play.<\/p>\n\n\n\n<p>Return the winner of the game if it exists (<em>A<\/em>&nbsp;or&nbsp;<em>B<\/em>), in case the game ends in a draw return &#8220;Draw&#8221;, if there are still movements to play return &#8220;Pending&#8221;.<\/p>\n\n\n\n<p>You can assume that&nbsp;<code>moves<\/code>&nbsp;is&nbsp;<strong>valid<\/strong>&nbsp;(It follows the rules of Tic-Tac-Toe),&nbsp;the grid is initially empty and&nbsp;<em>A<\/em>&nbsp;will play&nbsp;<strong>first<\/strong>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]\n<strong>Output:<\/strong> \"A\"\n<strong>Explanation:<\/strong> \"A\" wins, he always plays first.\n\"X  \"    \"X  \"    \"X  \"    \"X  \"    \"<strong>X<\/strong>  \"\n\"   \" -&gt; \"   \" -&gt; \" X \" -&gt; \" X \" -&gt; \" <strong>X<\/strong> \"\n\"   \"    \"O  \"    \"O  \"    \"OO \"    \"OO<strong>X<\/strong>\"\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]\n<strong>Output:<\/strong> \"B\"\n<strong>Explanation:<\/strong> \"B\" wins.\n\"X  \"    \"X  \"    \"XX \"    \"XXO\"    \"XXO\"    \"XX<strong>O<\/strong>\"\n\"   \" -&gt; \" O \" -&gt; \" O \" -&gt; \" O \" -&gt; \"XO \" -&gt; \"X<strong>O<\/strong> \" \n\"   \"    \"   \"    \"   \"    \"   \"    \"   \"    \"<strong>O<\/strong>  \"\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]\n<strong>Output:<\/strong> \"Draw\"\n<strong>Explanation:<\/strong> The game ends in a draw since there are no moves to make.\n\"XXO\"\n\"OOX\"\n\"XOX\"\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> moves = [[0,0],[1,1]]\n<strong>Output:<\/strong> \"Pending\"\n<strong>Explanation:<\/strong> The game has not finished yet.\n\"X  \"\n\" O \"\n\"   \"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= moves.length &lt;= 9<\/code><\/li><li><code>moves[i].length == 2<\/code><\/li><li><code>0 &lt;= moves[i][j] &lt;= 2<\/code><\/li><li>There are no repeated elements on&nbsp;<code>moves<\/code>.<\/li><li><code>moves<\/code>&nbsp;follow the rules of tic tac toe.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(1)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string tictactoe(vector<vector<int>>& moves) {\n    vector<vector<string>> b(3, vector<string>(3, \"#\"));\n    bool A = true;\n    for (const auto& move : moves) {\n      b[move[0]][move[1]] = A ? \"A\" : \"B\";\n      A = !A;\n    }\n    for (int i = 0; i < 3; ++i) {\n      if (b[i][0] == b[i][1] &#038;&#038; b[i][2] == b[i][1] &#038;&#038; b[i][0] != \"#\")\n        return b[i][0];\n      if (b[0][i] == b[1][i] &#038;&#038; b[2][i] == b[1][i] &#038;&#038; b[0][i] != \"#\")\n        return b[0][i];\n    }\n    if (b[0][0] == b[1][1] &#038;&#038; b[1][1] == b[2][2] &#038;&#038; b[1][1] != \"#\")\n      return b[1][1];\n    if (b[2][0] == b[1][1] &#038;&#038; b[1][1] == b[0][2] &#038;&#038; b[1][1] != \"#\")\n      return b[1][1];\n    return moves.size() == 9 ? \"Draw\" : \"Pending\";\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Tic-tac-toe is played&nbsp;by&nbsp;two players&nbsp;A&nbsp;and&nbsp;B&nbsp;on a&nbsp;3&nbsp;x&nbsp;3&nbsp;grid. Here are the rules of Tic-Tac-Toe: Players take turns placing characters into empty squares (&#8221; &#8220;). The first player&nbsp;A&nbsp;always places&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[222,27,179,4],"class_list":["post-5904","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-easy","tag-game","tag-simulation","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5904","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5904"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5904\/revisions"}],"predecessor-version":[{"id":5907,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5904\/revisions\/5907"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5904"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5904"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5904"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}