PID459 / 最小费用多米诺
题目描述

在 N*M 的棋盘上互不覆盖地放置 1*2 和 2*1 的多米诺方块,有一些格子上有障碍,这些格子不能放置多米诺方块。在每个没有障碍的格子上有两个费用值,分别表示这个格子上横放和竖放多米诺方块所需的费用。试问存不存在一种放置多米诺的方案,能放满所有无障碍的格子。若存在,求出完成放置的最小费用;若不存在,求出最多能放置多少个多米诺。

数据规模

保证第一行的答案不超过 2^30。

对于 30% 的数据,N, M <= 5。

对于 80% 的数据,N, M 中至少有一个不超过8。

对于 100% 的数据,N, M <= 40。

备注

本题设有部分分,对于每种情况,如果你的程序只输出了第一行且答案正确,可以得到该测试点 70% 的分数。但是如果你的程序输出了放置方案而方案不正确,该测试点得0分。

[感谢题目作者wish]

输入格式

第一行两个正整数 N 和 M,表示棋盘共 N 行 M 列。

后为两个 N*M 的矩阵,分别表示棋盘每个格子横放和竖放多米诺的费用。费用为正整数,若费用为0,则格子是障碍格(保证障碍格两个费用均为0)。

输出格式

若存在至少一种放置方案,则第一行输出最小费用,后跟一个 N*M 的矩阵,表示最小费用方案。

若不存在满足要求的放置方案,则第一行输出最多能够放置多少个多米诺,后跟一个 N*M 的矩阵,输出一种放置方案。

方案可能有很多种,只需输出任意一种即可。

输出的方案中,0表示这个格子不放置多米诺,1表示这个格子的多米诺横放,2 表示这个格子的多米诺竖放。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论