1220.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1220 on 2006-05-18 at 15:11:47 */ 
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int SN = 1 << 20;
const int BN = 32;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 0, 0 } };
enum { JACK, JILL };

class Heap {
private:
	int size, d[SN], st[SN], o[SN];
public:
	void clear() { size = 0; memset(o, -1, sizeof(o)); }
	void push(const pii&);
	pii top() const { return pii(d[0], st[0]); }
	void pop();
};
void Heap::push(const pii& p) {
	int cd = p.first, cst = p.second;
	if(o[cst] == -1) { d[size] = cd; st[size] = cst; o[cst] = size++; }
	else if(o[cst] == SN || d[o[cst]] >= cd) return;
	else d[o[cst]] = cd;
	int i = o[cst], m = d[i];
	while(i != 0) {
		int prev = (i-1) / 2;
		if(m > d[prev]) { d[i] = d[prev]; st[i] = st[prev]; o[st[i]] = i; i = prev; }
		else break;
	}
	d[i] = m; st[i] = cst; o[cst] = i;
}
void Heap::pop() {
	o[st[0]] = SN;
	int p = d[0] = d[--size], ost = st[size];
	if(size == 0) return;
	int i = 0;
	while(true) {
		int ls = i*2+1, rs = i*2+2, b = ls;
		if(ls >= size) break;
		if(rs < size && d[rs] > d[ls]) b = rs;
		if(p < d[b]) { d[i] = d[b]; st[i] = st[b]; o[st[i]] = i; i = b; }
		else break;
	}
	d[i] = p; st[i] = ost; o[ost] = i;
}


Heap Q;
char map[BN][BN];
int n;

bool legal(int, int, int);
inline int hash(int a, int b, int c, int d) { return a | (b<<5) | (c<<10) | (d<<15); }
inline int dis(int kx, int ky, int lx, int ly) { return (kx-lx)*(kx-lx)+(ky-ly)*(ky-ly); }
double dijkstra(int, int, int, int);

int main()
{
	int i, j;

	while(scanf("%d\n", &n) != EOF && n != 0) {
		int jkx, jky, jlx, jly;
		for(i = 0; i < n; i++) {
			gets(map[i]);
			for(j = 0; j < n; j++)
				if(map[i][j] == 'H') { jkx = i; jky = j; }
				else if(map[i][j] == 'h') { jlx = i; jly = j; }
		}
		printf("%.2lf\n", sqrt(1.0*dijkstra(jkx, jky, jlx, jly)));
	}
	
	return 0;
}

bool legal(int x, int y, int p)
{
	if(x < 0 || x == n || y < 0 || y == n || map[x][y] == '*') return false;
	else if(p == JACK) return !islower(map[x][y]);
	else return !isupper(map[x][y]);
}
double dijkstra(int jkx, int jky, int jlx, int jly)
{
	int i, j; Q.clear();
	Q.push(pii(dis(jkx, jky, jlx, jly), hash(jkx, jky, jlx, jly)));
	while(true) {
		pii p = Q.top(); Q.pop();
		int d = p.first, st = p.second;
		int kx = st&31, ky = (st>>5)&31, lx = (st>>10)&31, ly = (st>>15)&31;
		if(map[kx][ky] == 'S' && map[lx][ly] == 's') return d;
		for(i = 0; i < 4; i++) {
			if(map[kx][ky] == 'S') i = 4;
			int nkx = kx+DIR[i][0], nky = ky+DIR[i][1];
			if(!legal(nkx, nky, JACK)) continue;
			for(j = 0; j < 4; j++) {
				if(map[lx][ly] == 's') j = 4;
				int nlx = lx+DIR[j][0], nly = ly+DIR[j][1];
				if(!legal(nlx, nly, JILL)) continue;
				int nd = min(d, dis(nkx, nky, nlx, nly));
				Q.push(pii(nd, hash(nkx, nky, nlx, nly)));
			}
		}
	}
}