2024-01-24：用go语言，已知一个n*n的01矩阵， 只能通过通过行交换、或者列交换的方式调整矩阵， 判断这个矩阵的对角

2024-01-24：用go语言，已知一个n*n的01矩阵，

只能通过通过行交换、或者列交换的方式调整矩阵，

判断这个矩阵的对角线是否能全为1，如果能返回true，不能返回false。

我们升级一下:

已知一个n*n的01矩阵，

只能通过通过行交换、或者列交换的方式调整矩阵，

判断这个矩阵的对角线是否能全为1，如果不能打印-1。

如果能，打印需要交换的次数，并且打印怎么交换。

来自网易。

答案2024-01-24：

来自左程云。

灵捷3.5

大体步骤如下：

1.遍历矩阵的每一行和每一列，统计每行和每列的1的个数。

2.如果某一行或某一列的1的个数超过n/2（n为矩阵的大小），则无法通过交换操作使得对角线上的元素全为1，直接输出-1。

3.创建一个长度为n的数组rowOnes和colOnes，分别存储每行和每列的1的个数。

4.创建一个长度为n的二维数组swap，用于记录交换操作。

5.从第一行开始，逐行遍历矩阵，对于每一行，检查是否需要进行交换：

• 如果该行的1的个数小于n/2，则说明需要进行行交换，找到一行与其交换，并更新swap数组。

6.接着从第一列开始，逐列遍历矩阵，对于每一列，检查是否需要进行交换：

• 如果该列的1的个数小于n/2且当前行没有进行过行交换，则说明需要进行列交换，找到一列与其交换，并更新swap数组。

7.最后，检查矩阵的对角线是否全为1：

• 逐行遍历矩阵，如果某一行的对角线元素不为1，则说明无法满足条件，输出-1。

8.如果能够满足条件，则输出交换次数k和交换操作：

• 遍历swap数组，输出每次交换的行号和列号。

总的时间复杂度为O(n^2)，其中n为矩阵的大小。

总的额外空间复杂度为O(n)，用于存储rowOnes、colOnes和swap数组。

go完整代码如下：

package main

import (

"fmt"

)

var out [1000][2]int

func main() {

inputs := []int{2,

0, 1,

1, 0,

2,

1, 0,

1, 0}

ii := 0

n := inputs[ii]

ii++

graph := make([][]int, n)

for i := 0; i < n; i++ {

graph[i] = make([]int, n)

for j := 0; j < n; j++ {

graph[i][j] = inputs[ii]

ii++

}

}

t := km(graph)

fmt.Println(t)

for i := 0; i < t; i++ {

fmt.Printf("R %d %d\n", out[i][0]+1, out[i][1]+1)

}

}

func km(graph [][]int) int {

N := len(graph)

lx := make([]int, N)

ly := make([]int, N)

match := make([]int, N)

x := make([]bool, N)

y := make([]bool, N)

slack := make([]int, N)

invalid := int(1e9)

for i := 0; i < N; i++ {

match[i] = -1

lx[i] = -invalid

for j := 0; j < N; j++ {

lx[i] = max(lx[i], graph[i][j])

}

ly[i] = 0

}

for from := 0; from < N; from++ {

for i := 0; i < N; i++ {

slack[i] = invalid

}

fillBoolSlice(x, false)

fillBoolSlice(y, false)

for !dfs(from, x, y, lx, ly, match, slack, graph) {

d := invalid

for i := 0; i < N; i++ {

if !y[i] && slack[i] < d {

d = slack[i]

}

}

for i := 0; i < N; i++ {

if x[i] {

lx[i] -= d

}

if y[i] {

ly[i] += d

}

}

fillBoolSlice(x, false)

fillBoolSlice(y, false)

}

}

ans := 0

for i := 0; i < N; i++ {

ans += (lx[i] + ly[i])

}

if ans < N {

return -1

}

t := 0

for i := 0; i < N; i++ {

u, v := match[i], i

if u != v {

out[t][0] = v

out[t][1] = u

for j := i + 1; j < N; j++ {

if match[j] == v {

match[j] = u

}

}

t++

}

}

return t

}

func dfs(from int, x, y []bool, lx, ly, match, slack []int, graph [][]int) bool {

N := len(graph)

x[from] = true

for to := 0; to < N; to++ {

if !y[to] {

d := lx[from] + ly[to] - graph[from][to]

if d != 0 {

slack[to] = min(slack[to], d)

} else {

y[to] = true

if match[to] == -1 || dfs(match[to], x, y, lx, ly, match, slack, graph) {

match[to] = from

return true

}

}

}

}

return false

}

func fillBoolSlice(arr []bool, value bool) {

for i := 0; i < len(arr); i++ {

arr[i] = value

}

}

func max(a, b int) int {

if a > b {

return a

}

return b

}

func min(a, b int) int {

if a < b {

return a

}

return b

}

在这里插入图片描述python代码如下：

# -*-coding:utf-8-*-

def km(graph):

N = len(graph)

lx = [-float('inf')] * N

ly = [0] * N

match = [-1] * N

x = [False] * N

y = [False] * N

slack = [float('inf')] * N

invalid = int(1e9)

for i in range(N):

lx[i] = max(graph[i])

for from_ in range(N):

for i in range(N):

slack[i] = invalid

x = [False] * N

y = [False] * N

while not dfs(from_, x, y, lx, ly, match, slack, graph):

d = invalid

for i in range(N):

if not y[i] and slack[i] < d:

d = slack[i]

for i in range(N):

if x[i]:

lx[i] -= d

if y[i]:

ly[i] += d

x = [False] * N

y = [False] * N

ans = 0

for i in range(N):

ans += (lx[i] + ly[i])

if ans < N:

return -1

t = 0

out = [[0, 0]] * N

for i in range(N):

u, v = match[i], i

if u != v:

out[t][0] = v

out[t][1] = u

for j in range(i + 1, N):

if match[j] == v:

match[j] = u

t += 1

return t, out

def dfs(from_, x, y, lx, ly, match, slack, graph):

N = len(graph)

x[from_] = True

for to in range(N):

if not y[to]:

d = lx[from_] + ly[to] - graph[from_][to]

if d != 0:

slack[to] = min(slack[to], d)

else:

y[to] = True

if match[to] == -1 or dfs(match[to], x, y, lx, ly, match, slack, graph):

match[to] = from_

return True

return False

inputs = [2, 0, 1, 1, 0, 2, 1, 0, 1, 0]

ii = 0

n = inputs[ii]

ii += 1

graph = [[0] * n for _ in range(n)]

for i in range(n):

for j in range(n):

graph[i][j] = inputs[ii]

ii += 1

t, out = km(graph)

print(t)

for i in range(t):

print("R", out[i][0] + 1, out[i][1] + 1)

在这里插入图片描述