• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode782.变为棋盘|TransformtoChessboard

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

An N x N board contains only 0s and 1s. In each move, you can swap any 2 rows with each other, or any 2 columns with each other.

What is the minimum number of moves to transform the board into a "chessboard" - a board where no 0s and no 1s are 4-directionally adjacent? If the task is impossible, return -1.

Examples:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation:
One potential sequence of moves is shown below, from left to right:

0110     1010     1010
0110 --> 1010 --> 0101
1001     0101     1010
1001     0101     0101

The first move swaps the first and second column.
The second move swaps the second and third row.

Input: board = [[0, 1], [1, 0]]
Output: 0
Explanation:
Also note that the board with 0 in the top left corner,
01
10

is also a valid chessboard.

Input: board = [[1, 0], [1, 0]]
Output: -1
Explanation:
No matter what sequence of moves you make, you cannot end with a valid chessboard.

Note:

  • board will have the same number of rows and columns, a number in the range [2, 30].
  • board[i][j] will be only 0s or 1s.

一个 N x N的 board 仅由 0 和 1 组成 。每次移动,你能任意交换两列或是两行的位置。

输出将这个矩阵变为 “棋盘” 所需的最小移动次数。“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。如果不存在可行的变换,输出 -1。

示例:
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:
一种可行的变换方式如下,从左到右:

0110     1010     1010
0110 --> 1010 --> 0101
1001     0101     1010
1001     0101     0101

第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。

输入: board = [[0, 1], [1, 0]]
输出: 0
解释:
注意左上角的格值为0时也是合法的棋盘,如:

01
10

也是合法的棋盘.

输入: board = [[1, 0], [1, 0]]
输出: -1
解释:
任意的变换都不能使这个输入变为合法的棋盘。 

提示:

  • board 是方阵,且行列数的范围是[2, 30]
  • board[i][j] 将只包含 0或 1

Runtime: 52 ms
Memory Usage: 18.7 MB
 1 class Solution {
 2     func movesToChessboard(_ board: [[Int]]) -> Int {
 3         var n:Int = board.count
 4         var rowSum:Int = 0
 5         var colSum:Int = 0
 6         var rowDiff:Int = 0
 7         var colDiff:Int = 0
 8         for i in 0..<n
 9         {
10             for j in 0..<n
11             {
12                 if board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] != 0
13                 {
14                     return -1
15                 }
16             }
17         }
18         for i in 0..<n
19         {
20             rowSum += board[0][i]
21             colSum += board[i][0]
22             rowDiff += (board[i][0] == i % 2 ? 1 : 0)
23             colDiff += (board[0][i] == i % 2 ? 1 : 0)
24         }
25         if n / 2 > rowSum || rowSum > (n + 1) / 2 {return -1}
26         if n / 2 > colSum || colSum > (n + 1) / 2 {return -1}
27         if n % 2 != 0
28         {
29             if rowDiff % 2 != 0 {rowDiff = n - rowDiff}
30             if colDiff % 2 != 0 {colDiff = n - colDiff}
31         }
32         else
33         {
34             rowDiff = min(n - rowDiff, rowDiff)
35             colDiff = min(n - colDiff, colDiff)
36         }
37         return (rowDiff + colDiff) / 2
38     }
39 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode257.二叉树的所有路径|BinaryTreePaths发布时间:2022-07-13
下一篇:
swift对象存储发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap