
ZOJ Problem Set  3308
In order to celebrate the 8th anniversary of ZOJ, ZJU ACM team members are playing a game named "Move the Knights". Given a chessboard with size R x C. The row number and column number are all indexed from 1, each grid has a power value P_{(row,col)} related with it. There are 3 kinds of knights in this game, called "Gold Knight", "Silver Knight" and "Bronze Knight", respectively. They can only be moved to one of the eight positions as the following gragh shows, and cannot be moved out of the board of course. When transferred from one position to another, the Knight will lose a certain quantity of energy according to the power value of the two girds and the type of the knight, for example, from Grid_{(row1,col1)} to Gird_{(row2,col2)}, Gold Knight will lose P_{(row1,col1)} x P_{(row2,col2)} energy, Silver Knight will lose P_{(row1,col1)} + P_{(row2,col2)} energy, and Bronze Knight will loss max( P_{(row1,col1)}, P_{(row2,col2)} ) energy. Initially, N knights are placed in black grids. The goal of this game is to move EXACTLY K (K <= N) Knights with minimal energy. Note that each Knight can be moved ONLY ONCE, and every grid can be occupied by one knight at most. The Grid_{(row,cow)} is black when and only when (row + col) mod 2 = 0. Input There are multiple cases(no more than 50). Each test case starts with a line, which contains 4 positive integers, R C N K (1 <= R, C <= 15, 1 <= N <= RxC/2, 1 <= K <= N). Then R lines follow, each contains C positive integers, the c^{th} integer of the r^{th} line inditating the power value (1 <= P_{(r,c)} <= 10) of that grid. Then N lines follow, each contains three positive integers: type ri ci (1 <= type <= 3, 1 <= ri <= R, 1 <= ci <= C). Type 1 indicates Gold Knight, type 2 indicates Silver Knight and type 3 indicates Bronze Knight, ri and ci are the position of that knight, it is guaranteed that Grid_{(ri,ci)} are all black grids. Output For each test case, output a single line containing the minimal energy lost when the K knights moved. If there is no solution, output 1 instead. Sample Input 3 4 2 2 1 1 1 1 2 2 2 2 3 2 3 4 2 1 1 1 1 3 3 3 1 1 1 1 1 2 2 2 3 3 3 3 2 2 Sample Output 5 1 Hint
Case 1: Move the Silver Kight from Grid(1,1) to Grid(2,3) and move the Gold Kight from Grid(1,3) to Grid(3,2) achieve the goal. Case 2: You hava no way to move the Bronze Knight, just output 1. Author: FU, Changlin Source: ZOJ 8th Anniversary Contest 