问题 5489 --魔法阵-【2014暑期训练】T7Day1T3

5489: 魔法阵-【2014暑期训练】T7Day1T3

时间限制: 1 Sec  内存限制: 256 MB
提交: 25  解决: 8
[提交][状态][讨论版][命题人:]

题目描述

魔法阵

【问题描述】

魔法阵是一个n*m的格子(高n,宽m),n*m为偶数。佳佳手中有n*m个宝石(以1~n*m编号)。佳佳从最右上角的格子开始走,从一个格子可以走到上、下、左、右4个相邻的格子,但不能走出边界。每个格子必须且仅能到过1次,这样佳佳一共走了n*m个格子停止(随便停哪里)。佳佳每进入一个格子,就在该格子里放入一颗宝石。他是按顺序放的,也就是说——第i个进入的格子放入i号宝石。
   如果两颗宝石的编号对n*m/2取模的值相同,则认为这两颗宝石相互之间有微妙的影响。也就是说,我们按照宝石的编号对n*m/2取模的值,将宝石分成n*m/2对,其中每对都恰有两颗宝石。对于每一对宝石,设第一颗宝石在第a行第b列,另一颗宝石在第c行第d列,那么定义这2个宝石的魔力影响值为k1*|a-c|+k2*|b-d|。
   需要你求出的是,在所有合乎题意的宝石摆放方案中,所有成对的宝石间的最大魔力影响值的最小值为多少。换句话说,如果我们定义对n*m/2取模的值为i的一对宝石的魔力影响值为a[i]。

你需要求出的就是max{a[i]|i=0,1,2...}的最小值。

【文件输入】

只有一行用空格隔开的4个整数,分别是n、m、k1、k2。

【文件输出】

只需输出一个整数,即题目所要求的“所有成对的宝石间的最大魔力影响值的最小值”。

【输入样例】

2 2 2 2

【输出样例】

4

【数据规模】

对于100%的数据,n*m<=50,0<k1,k2<=32767。

提示


首先,这道题应该是比较典型的深搜,需要搜索各种可能的n*m矩阵中的路径。



但是,单纯的、不加任何剪枝的搜索大约只能过3组。我们在这道题中必须用到搜索中最典型的两种剪枝:最优性剪枝和可行性剪枝。



最优性剪枝的思路相对简单:当我们搜索到某一条路径,发现它的某个k1*|a-c|+k2*|b-d|已经超过了当前已经求出的最优解,那么肯定是不用沿这条路径继续搜索下去了,直接回溯即可。



可行性剪枝的基本思路就是:在搜索过程中判断当前是否还能够走成一条完整的路径。简单来说,当未走到过的方格是不连通的两个部分时,肯定就无法走完剩下的路径,必须剪枝。具体的判断方法是:如果 (当前方格的上下两个方格都被访问过 且 左右两个方格都没有被访问过) 或者 (当前方格的左右两个方格都被访问过 且 上下两个方格都没有被访问过),则可以剪枝。这样可以在O(1)的时间内做到可行性判断。

来源

 

[提交][状态]