2209.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2209 on 2006-04-18 at 12:03:15 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int SIZE = 61;
const int COL[] = { 5, 6, 7, 8, 9, 8, 7, 6, 5 };
const int SUM[] = { 0, 5, 11, 18, 26, 35, 43, 50, 56 };
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { -1, 1 }, { 1, -1 }, { 1, 0 } };
const char SOD_TYPE[] = "GSM";
const char TER_TYPE[] = "FWHMU";
const int INF = 1 << 20;

vector<int> nei[SIZE];
char map[SIZE];
int war[SIZE];

bool legal(int r, int c) { return r >= 0 && r < 9 && c >= 0 && c < COL[r]; }
int pos(char, char);
int pay(char);
bool vaild(int, int, bool);
int walk(int, int);

int main()
{
	int t, T, i, j, k;
	
	for(i = 'A'; i <= 'I'; i++)
		for(j = 0; j < COL[i-'A']; j++) {
			char jj = j+'1';
			if(i < 'E') jj += 4+'A'-i;
			int now = pos(i, jj); nei[now].clear();
			for(k = 0; k < 6; k++) {
				char x = i+DIR[k][0], yy = jj+DIR[k][1], y = j+DIR[k][1];
				if(legal(x-'A', y)) nei[now].push_back(pos(x, yy));
			}
		}
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		memset(war, -1, sizeof(war));
		for(i = 0; i < SIZE; i++) scanf("\n%c", &map[i]);
		int b, w; scanf("%d %d", &b, &w);
		for(i = 0; i < b+w; i++) {
			char tp, x, y; scanf("\n%c\n%c%c", &tp, &x, &y);
			for(j = 0; tp != SOD_TYPE[j]; j++);
			int co = pos(x, y), so = (j<<1)|((i<b)?0:1);
			war[co] = so;
		}
		printf("Game #%d\n", t);
		int n; scanf("%d", &n);
		for(i = 1; i <= n; i++) {
			char x1, y1, x2, y2; scanf("\n%c%c\n%c%c", &x1, &y1, &x2, &y2);
			int b = pos(x1, y1), e = pos(x2, y2), cost = walk(b, e);
			printf("Move #%d (%c%c -> %c%c): ", i, x1, y1, x2, y2);
			if(cost > 10) printf("Unsuccessful\n");
			else {
				printf("Successful (%d points left)\n", 10-cost);
				war[e] = war[b]; war[b] = -1;
			}
		}
	}
	
	return 0;
}

int walk(int b, int e)
{
	if(war[b] == -1 || war[e] != -1) return INF;
	int i, j, d[SIZE];
	bool vst[SIZE] = { false };
	for(i = 0; i < SIZE; i++) d[i] = INF;
	d[b] = 0;
	for(i = 0; i < SIZE; i++) {
		int mind = INF, mini;
		for(j = 0; j < SIZE; j++)
			if(!vst[j] && mind > d[j])
				{ mind = d[j]; mini = j; }
		if(mind == INF || mini == e) break;
		vst[mini] = true;
		for(j = 0; j < (int)nei[mini].size(); j++) {
			int o = nei[mini][j];
			if(d[o] > d[mini]+pay(map[o]) && vaild(war[b], o, o == e))
				d[o] = d[mini]+pay(map[o]);
		}
	}
	return d[e];
}
int pos(char x, char y)
{
	int r = x - 'A', c = y - '1';
	if(r >= 4) return SUM[r] + c;
	else return SUM[r] + c-4+r;
}
int pay(char ter)
{
	int i;
	for(i = 0; ter != TER_TYPE[i]; i++);
	if(i == 4) return INF;
	else return i+1;
}
bool vaild(int type, int o, bool end)
{
	int i, tp = type >> 1, opp = (tp+2)%3*2+1-(type&1);
	for(i = 0; !end && i < (int)nei[o].size(); i++)
		if(war[nei[o][i]] == opp) return false;
	if(war[o] != -1) return (type&1) == (war[o]&1);
	return true;
}