问题 3240 --复杂的审批

3240: 复杂的审批

题目描述

   魔法学院是一个庞大的机构,一件事情能否被顺利执行需要通过各级领导的层层审批,这天,墨老师因为研制基因武器的计划需要审批,他来到了学院的办公大楼。办公大楼是一座M层的大楼,1≤M≤100。每层楼都有N个办公室,编号为1,…,N(1≤N≤500),每个办公室有一个领导。计划必须要让第M层的某个领导审批通过才行。
每个领导都要满足下面三个条件之一才会给审批通过:
1. 这个领导在1楼。
2. 计划已经给这个领导的正楼下(房间号相同)的领导审批通过了。
3. 计划已经给这个领导的相邻房间(房间号相差1,楼层相同)的领导审批通过了。
墨老师每到一个领导处审批都要付出一番口舌说服,这是必须付出的代价,代价值不超过1000000000。
请找出代价最小的审批路线,使计划生效。

输入

第1行两个整数M和N。
接下来M行每行N个整数,第i行第j个数表示说服第i层的第j个领导的代价。

输出

按顺序打出你经过的房间的编号,每行一个数。
如果有多条费用最小的路线,输出最短的路径。

样例输入输出

输入#1 复制
3 4
10 10 1 10
2 2 2 10
1 10 10 10
输出#1 复制
3
3
2
1
1

提示

序号 标题 作者 发表时间 费用 订购数 操作