2958 Pizza delivery

2958 -- Pizza delivery

すこし早いけれど，今週のPKU．
今回のプログラムは胡散臭いので，日記に書こうか悩みました．

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static int getCost(int x, int y, int[][] costs, int[][] map) {
		
		if( x < 0 || y < 0 || x >= map.length || y >= map[0].length ) {
			return Integer.MAX_VALUE;
		}
		
		if( costs[x][y] != -1 ) {
			return costs[x][y];
		}
		
		int cost = 0;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if ( i != x || j != y )
				   cost += map[i][j] * ( Math.abs(i-x) + Math.abs(j-y) );
			}
		}
		
		costs[x][y] = cost;
		
		return cost;
	}
	
	public static int search(int x, int y, int[][] costs, int[][] map) {
		
		int[][] rotate = {{1,0},{0,1},{-1,0},{0,-1}};
		int min = getCost(x, y, costs, map);
		for(int[] i : rotate 	) {
			if( min > getCost(x+i[0], y+i[1], costs, map) ) {
				min = Math.min(min, search(x+i[0], y+i[1], costs, map));
			}
		}
		return min;
	}
	
	public static void main(String[] args) {
		
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		for(;n-->0;){
			int w=s.nextInt();
			int h=s.nextInt();
			int[][] map=new int[h][w];
			for (int x = 0; x < map.length; x++) {
				for (int y = 0; y < map[x].length; y++) {
					map[x][y]=s.nextInt();
				}
			}
			
			int[][] costs=new int[h][w];
			
			for(int i=0;i<costs.length;++i) {
				Arrays.fill(costs[i], -1);
			}
			
			System.out.println(search(0, 0, costs, map) + " blocks");
			
		}
	}
}

最初に総当りのプログラムを書いてみたものの，やっぱり時間超過．O(n^4)が通るはずがない．
計算を少なくなるようなアルゴリズムを考えたものの，うまくいかかず，コストを調べる箇所を減らす方法を考えた．答えが左半分にあるとか，真ん中にあるとか，いろいろ試してみたものの，どれもWrong Answerどころか時間超過していた．こんな胡散臭いやり方なのに，まだ時間が足らないのかよとか考えつつ，最後はこんな形になった．

アルゴリズムはコストを計算する箇所を逐次的に調べていく方法です．(0,0)から初めて，上下左右のコストを調べ，自分よりも小さかった場合そのマスに移動して，いまのと同じことを繰り返していく．この方法だと，局所解があった場合に失敗してしまうのだけども，テストケースにはないらしくAcceptされた．どう考えても局所解があるので，チートコードです．