[Swift]LeetCode913.猫与老鼠|CatandMouse

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9858200.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

Mouse starts at node 1 and goes first, Cat starts at node 2 and goes second, and there is a Hole at node 0.

During each player's turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)

Then, the game can end in 3 ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (ie. the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.

Example 1:

Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Explanation:
4---3---1
|   |
2---5
 \ /
  0

Note:

3 <= graph.length <= 50
It is guaranteed that graph[1] is non-empty.
It is guaranteed that graph[2] contains a non-zero element.

一个无向图上的游戏由两个玩家组成，鼠标和猫，他们交替轮流。

该图如下给出：graph[a]是所有节点的列表，b例如ab图的边缘。

鼠标从节点1开始并先行，Cat从节点2开始然后变为第二个，并且节点0处有一个孔。

在每个玩家的回合中，他们必须沿着图表的一个边缘行进，以满足它们的位置。例如，如果鼠标位于节点1，则它必须前往任何节点graph[1]。

此外，Cat不允许移动到孔（节点0）。

然后，游戏可以以3种方式结束：

如果Cat占用与鼠标相同的节点，则Cat获胜。
如果鼠标到达了洞，鼠标就会获胜。
如果一个位置被重复（即，玩家处于与前一回合相同的位置，并且轮到同一个玩家），则该游戏是平局。

给定a graph，并假设两个玩家都玩得最佳，1 如果游戏是由鼠标赢得，2 如果游戏是由Cat赢得，并且0 游戏是平局，则返回。

例1：

输入：[[2,5]，[3]，[0,4,5]，[1,4,5]，[2,3]，[0,2,3]] 
输出：0
 说明：
 4- --3 --- 1
| |
2 --- 5
 \ / \
  0

注意：

3 <= graph.length <= 50
保证graph[1]非空。
保证graph[2]包含非零元素。

140ms

 1 class Solution {
 2     func catMouseGame(_ graph: [[Int]]) -> Int {
 3         var n:Int = graph.count
 4         var win:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: n*n), count: 2)
 5         //mc
 6         for i in 0..<n
 7         {
 8             win[0][i] = 1
 9             win[1][i] = 1
10         }
11         for i in 0..<n
12         {
13             win[0][i*n+i] = 2
14             win[1][i*n+i] = 2
15         }
16         
17         while(true)
18         {
19             var anew:Bool = false
20             for m in 0..<n
21             {
22                 inner:
23                 for c in 1..<n
24                 {
25                     if win[0][m*n+c] == 0
26                     {
27                         var und:Bool = false
28                         for e in graph[m]
29                         {
30                             if win[1][e*n+c] == 1
31                             {
32                                 win[0][m*n+c] = 1
33                                 anew = true
34                                 continue inner
35                             }
36                             if win[1][e*n+c] == 0
37                             {
38                                     und = true
39                             }
40                         }
41                         if !und
42                         {
43                             win[0][m*n+c] = 2
44                             anew = true
45                         }
46                     }
47                 }
48             }
49             for c in 1..<n
50             {
51                 inner:
52                 for m in 0..<n
53                 {
54                     if win[1][m*n+c] == 0
55                     {
56                         var und:Bool = false
57                          for e in graph[c]
58                         {
59                             if e == 0 {continue}
60                             if win[0][m*n+e] == 2
61                             {
62                                 win[1][m*n+c] = 2
63                                 anew = true
64                                 continue inner
65                             }
66                             if win[0][m*n+e] == 0
67                             {
68                                 und = true
69                             }
70                         }
71                         if !und
72                         {
73                              win[1][m*n+c] = 1
74                             anew = true
75                         }
76                     }
77                 }
78             }
79             if !anew {break}
80         }
81         return win[0][1*n+2]
82     }
83 }