Skip to content

1052: 填字游戏

题目

题目描述

皮哦哦又遇到了一个不会的问题,现在他来请教你:

皮哦哦在玩一个填数游戏,这个游戏是在一个大小 $n$ 行 $m$ 列的矩阵上开展的,填数的规则如下

  1. 每行由自然数 $1\sim m$ 填满,每行中每个数字用且只能用一次
  2. 相邻的自然数不会出现在相邻的方格中,包括左右相邻和上下相邻
  3. 第 $i$ 列的得分为第 $i$ 列所有自然数的总和 $s\times i$ ,总得分为 $m$ 列得分之和
    皮哦哦当然想拿最高分,所以请你告诉 TA 填数的方案

输入格式

第一行,两个正整数 $n,m$

接下来一个矩阵,矩阵的每一行为一个非负数,$0$ 表示需要填充,非 $0$ 表示已经填充过且不能被更改。

输出格式

输出共一行,包含一个正整数,表示最大总分。

样例输入

text 2 5 1 3 0 2 0 4 0 3 5 2

样例输出

text 95

数据范围

对于100%的数据,$3\leq n, m\leq 7$,$0$ 的个数 $\leq n\times m$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!