782. Transform to Chessboard

Stella981
• 阅读 268

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.

Approach #1: Array. [Math]

class Solution {
    public int movesToChessboard(int[][] b) {
        int N = b.length, rowSum = 0, colSum = 0, rowSwap = 0, colSwap = 0;
        for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
            if ((b[0][0] ^ b[i][0] ^ b[0][j] ^ b[i][j]) == 1) return -1;
        for (int i = 0; i < N; ++i) {
            rowSum += b[0][i];
            colSum += b[i][0];
            if (b[i][0] == i % 2) rowSwap++;
            if (b[0][i] == i % 2) colSwap++;
        }
        if (rowSum != N/2 && rowSum != (N+1)/2) return -1;
        if (colSum != N/2 && colSum != (N+1)/2) return -1;
        if (N % 2 == 1) {
            if (colSwap % 2 == 1) colSwap = N - colSwap;
            if (rowSwap % 2 == 1) rowSwap = N - rowSwap;
        } else {
            colSwap = Math.min(N-colSwap, colSwap);
            rowSwap = Math.min(N-rowSwap, rowSwap);
        }
        return (colSwap + rowSwap) / 2;
    }
}

Analysis:

In a valid chess board, there are 2 and only 2 kinds of rows and one is inverse to the other. For example if there is a row 0101001 in the board, any other row must be either 0101001 or 1010110.

The same for colums.

A corollary is that, any rectangle inside the board with corners top left, top right, bottom left, bottom right must be 4 zeros or 2 zeros 2 ones or 4 ones.

Another important property is that every row and column has half ones. Assume the board is N * N:

If N = 2  * K, every row and every colum has K ones and K zeros.

If N = 2 * K + 1, every row and every col has K ones and K + 1 zeros or K + 1 ones and K zeros.

Since the swap process does not break this property, for a fiven board to be valid, this property must hold.

These two conditions are necessary and sufficient condition for a calid chessboard.

Once we know it is a valid cheese board, we start to count swaps.

Basic on the property above, when we arange the first row, we are actually moving all columns.

I try to arrange one row into 01010 and 10101 and I count the number of swap.

In case of N even, I take the minimum swaps, because both are possible.

In case of N odd, I take the even swaps.

Because when we make a swap, we move 2 columns or 2 rows at the same time.

So col swaps and row swaps shoule be same here.

Reference:

https://leetcode.com/problems/transform-to-chessboard/discuss/114847/C%2B%2BJavaPython-Solution-with-Explanation

点赞
收藏
评论区
推荐文章
光头强的博客 光头强的博客
2个月前
Java面向对象试题
1、 请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。 创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现 接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿 吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
2个月前
css问题
1、 在IOS中图片不显示(给图片加了圆角或者img没有父级) <div<img src""/</div div {width: 20px; height: 20px; borderradius: 20px; overflow: h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
小森森 小森森
2个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本 欢迎添加左边的微信一起探讨!项目地址:](https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n) \2. Bug修复更新日历 2. 情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意), \ \ 和 注意
晴空闲云 晴空闲云
2个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。 盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
> MemFire Cloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Easter79 Easter79
1年前
swap空间的增减方法
(1)增大swap空间 去激活swap交换区: #swapoff -v /dev/vg00/lvswap 扩展交换lv: #lvextend -L 10G /dev/vg00/lvswap 重新生成swap交换区: #mkswap /dev/vg00/lvswap 激活新生成的交换区: #swapon -v /dev/vg00/lvswap
可莉 可莉
1年前
0312. Burst Balloons (H)
Burst Balloons (H) ================== 题目 -- Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by array `nums`. You are asked
Wesley13 Wesley13
1年前
PHP创建多级树型结构
<!-- lang: php --> <?php $area = array( array('id'=>1,'pid'=>0,'name'=>'中国') ,array('id'=>5,'pid'=>0,'name'=>'美国') ,array('id'=>2,'pid'=>1,'name'=>'吉林') ,array('id'=>4,'pid'=>2,'n
Stella981 Stella981
1年前
LeetCode 767. Reorganize String
Given a string `S`, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same. If possible, output any possible result.  If no
helloworld_28799839 helloworld_28799839
2个月前
常用知识整理
# Javascript ## 判断对象是否为空 ```js Object.keys(myObject).length === 0 ``` ## 经常使用的三元运算 > 我们经常遇到处理表格列状态字段如 `status` 的时候可以用到 ``` vue