2341.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2341 on 2006-08-26 at 14:56:09 */ 
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 64;
const int TN = 128;
const int DIR[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

class City {
private:
	int h[N][N], r, c, step[N][N];
	int ax[N], ay[N], ah[N], an, srcx, srcy, disx, disy;
	bool go(int, int) const;
	bool see(int, int, int, int, int, int, bool) const;
	bool visible(int, int, int, int, int, int) const;
public:
	void make();
	int walk();
};
void City::make() {
	scanf("%d %d", &r, &c);
	for(int i = 0; i < r; i++)
		for(int j = 0; j < c; j++) scanf("%d", &h[i][j]);
	scanf("%d %d %d %d %d", &disx, &disy, &srcx, &srcy, &an);
	for(int i = 0; i < an; i++) scanf("%d %d %d", &ax[i], &ay[i], &ah[i]);
}
bool City::go(int x, int y) const {
	for(int i = 0; i < an; i++)
		if(visible(x, y, 0, ax[i], ay[i], ah[i])) return true;
	return false;
}
bool City::see(int x1, int y1, int z1, int x2, int y2, int z2, bool subx) const {
	int dx, dy, dz;
	if(x2 < x1) { swap(x1 ,x2); swap(y1, y2); swap(z1, z2); }
	dx = x2-x1; dy = y2-y1; dz = z2-z1;
	for(int cx = x1+1; cx <= x2; cx++) {
		double cy = 1.0*dy*(cx-x1)/dx+y1, cz = 1.0*dz*(cx-x1)/dx+z1;
		int ty1 = (int)floor(cy), ty2 = (int)ceil(cy-1);
		if(dy < 0) swap(ty1, ty2);
		if(subx) {
			if((cx != x2 && cz < h[cx][ty1]) || cz < h[cx-1][ty2]) return false;
		} else 
			if((cx != x2 && cz < h[ty1][cx]) || cz < h[ty2][cx-1]) return false;
	}
	return true;
}
bool City::visible(int x1, int y1, int z1, int x2, int y2, int z2) const {
	if(x1 == x2 || y1 == y2) return true;
	else return see(x1, y1, z1, x2, y2, z2, true) && see(y1, x1, z1, y2, x2, z2, false);
}
int City::walk() {
	if(disx == srcx && disy == srcy) return 0;
	queue<int> Q; memset(step, -1, sizeof(step));
	Q.push((srcx<<10)|srcy); step[srcx][srcy] = 0;
	while(!Q.empty()) {
		int p = Q.front(), x = p>>10, y = p&1023; Q.pop();
		for(int i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(cx < 0 || cx > r || cy < 0 || cy > c || step[cx][cy] != -1 || !go(cx, cy)) continue;
			step[cx][cy] = step[x][y]+10;
			if(cx == disx && cy == disy) return step[disx][disy];
			Q.push((cx<<10)|cy);
		}
	}
	return -1;
}

int main()
{
	int T;
	City city;

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		city.make();
		printf("%d\n", city.walk());
	}
	
	return 0;
}