03670: 计算鞍点

matrice, http://cs101.openjudge.cn/practice/03670

给定一个5*5的矩阵，每行只有一个最大值，每列只有一个最小值，寻找这个矩阵的鞍点。鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值。例如：在下面的例子中（第4行第1列的元素就是鞍点，值为8 ）。 11 3 5 6 9 12 4 7 8 10 10 5 6 9 11 8 6 4 7 2 15 10 11 20 25

输入

输入包含一个5行5列的矩阵

输出

如果存在鞍点，输出鞍点所在的行、列及其值，如果不存在，输出"not found"

样例输入

11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8  6 4 7 2
15 10 11 20 25

样例输出

4 1 8

证明鞍点最多只有一个：

反证法：已知一个鞍点（x, y），是第x行最大值，第y列最小值，假设存在另一个点（x', y'），且它是第x'行最大值，那么：

它是第x'行最大值 -> 它一定大于（x', y）这个点。
（x, y）是第y列的最小值 ->（x', y）一定大于（x, y）。
（x, y）它是第x行最大值 ->（x, y）一定大于（x, y'）从而有：(x', y') > (x', y) > (x, y) > (x, y')，那么（x', y'）不可能是第y'列的最小值，从而不存在第二个鞍点。

python

mx = []
board = [[-9]*5 for _ in range(5)]

for _ in range(5):
    mx.append(list(map(int, input().split())))

for i in range(5):
    tmp = sorted(mx[i])
    row_max = tmp[-1]
    idx = mx[i].index(row_max)
    board[i][idx] = 1

for j in range(5):
    res = [sub[j] for sub in mx]
    tmp = sorted(res)
    col_min = tmp[0]
    idx = res.index(col_min)
    if board[idx][j] == 1:
        board[idx][j] = 0

for i in range(5):    
    for j in range(5):
        if board[i][j] == 0:
            print(i+1, j+1, mx[i][j])
            exit()
else:
    print("not found")

python

a = [[int(x) for x in input().split()] for _ in range(5)]
for i in range(5):
    maximum = a[i][0]
    maxindex = 0
    for j in range(1, 5):
        if a[i][j] > maximum:
            maximum = a[i][j]
            maxindex = j
    for j in range(5):
        if j != i and a[j][maxindex] <= maximum:
            break
    else:
        print(i+1, maxindex+1, maximum)
        break
else:
    print('not found')

2021fall-cs101，欧阳韵妍。

解题思路：先找出每行的最大值，再看看这个值是不是这一列的最小值，如果同一列里面有另外一个值比这个值小，就放弃这一行的这个值。

python

L = [[int(x) for x in input().split()] for i in range(5)]
for i in range(5):
    a = L[i].index(max(L[i]))
    for j in range(5):
        if L[j][a] < L[i][a]:
            break
    else:
        print(i+1, a+1, L[i][a])
        break
else:
    print("not found")

2021fall-cs101，留美琪。

通过将矩阵转置，便于找列的最小值。然后记录行最大和列最小的index，求交集。学到了转置可以用zip(*)来实现。

python

input_matrix = [[int(i) for i in input().split()] for _ in range(5)]
 
# 转置
matrix_T = list(map(list, zip(*input_matrix)))
 
row_max_index = []
col_min_index = []
 
for i in range(5):
    row_max_index.append((i, input_matrix[i].index(max(input_matrix[i]))))
    col_min_index.append((matrix_T[i].index((min(matrix_T[i]))), i))
 
ans = list(set(row_max_index) & set(col_min_index))
 
if len(ans) != 1:
    print("not found")
else:
    ans_index = ans[0]
    row = ans_index[0]
    col = ans_index[1]
    print(row+1, col+1, input_matrix[row][col])

03670: 计算鞍点 ​

03670: 计算鞍点