Maximum Winter Contest 2008 E問題(Problem E Exploring A Cave)

『Maximum Winter Contest 2008』のE問題
http://maximum.vc/PastProblems/Winter-Contest-2008/e/e.html

ダイクストラだけど・・・
『複数の異なる高さのマスが接する境界上の点の高さは、それらのうち最も高いマスの高さとする。』が罠！

#include <iostream>
using namespace std;

long long c[501][501];
long long m[501][501];
int w, h;

#define CHECK(a, b) (a >= 0 && b >= 0 && a < w && b < h && m[y][x] <= m[b][a])
#define CALC_COST(a, b) (m[y][x] - m[b][a]) * (m[y][x] - m[b][a])

void solv(int x, int y, long long hp){
	if(c[y][x] <= hp)return;
	c[y][x] = hp;
//	if(x ==0 && y == 0)return;

	for(int i = -1; i <= 1; i++)
		for(int j = -1; j <= 1; j++)
			if(i | j && CHECK(x + j, y + i) && (
				abs(i + j) == 1 || (
					m[y][x] <= m[y + i][x + j] && (
						(m[y][x] >= m[y + i][x] && m[y + i][x + j] >= m[y][x + j]) ||
						(m[y][x] >= m[y][x + j] && m[y + i][x + j] >= m[y + i][x])
					)
				)
			))solv(x + j, y + i, hp + CALC_COST(x + j, y + i));
}

int main(){
	while(cin >> w >> h, (w || h)){
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				scanf("%lld", &m[i][j]);
				c[i][j] = LLONG_MAX;
			}
		}
		int tx, ty;
		scanf("%d %d", &tx, &ty);
		solv(tx - 1, ty - 1, 0u);
		if(c[0][0] == LLONG_MAX)cout << "Impossible" << endl;
		else cout << c[0][0] << endl;
	}
	return 0;
}