b.cpp

ACM训练题解 最新版 共8题 ACM训练题解 最新版 共8题

// Problem B
// http://acm.uva.es/p/v109/10923.html
// Solution by semiconductor
#include	<cstdio>
#include	<cstdlib>
#include	<cstring>
#include	<algorithm>

using namespace std;
const char NUL = '\0';

int move[][2] = {
	{ -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, 
	{ 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }
};
const int row = 9, col = 8;
char board[9][9];
int en[9][2], ne;

inline int
Sgn(int n)
{
	if ( n == 0 ) return 0;
	else return n > 0 ? 1 : -1;
}

bool
Try(int d, int rs, int cs, char board[][col + 1], int en[][2], int ne)
{
	char nb[9][9];
	int en2[9][2], ne2;
	if ( ne == 0 ) return 1;
	if ( d == 9 ) return 0;
	for ( int k = 0; k < 8; k++ ) {
		int nr = rs + move[k][0], nc = cs + move[k][1];
		if ( nr < 0 || nr >= row || nc < 0 || nc >= col || board[nr][nc] != '.' ) continue;
		int i;
		for ( i = 0; i < ne; i++ ) {
			int r = en[i][0], c = en[i][1];
			int dr = Sgn(nr - r), dc = Sgn(nc - c);
			int rr = r + dr, cc = c + dc;
			if ( rr == nr && cc == nc ) break;
			en2[i][0] = rr;
			en2[i][1] = cc;
		}
		if ( i < ne ) continue;
		memcpy(nb, board, sizeof nb);
		for ( i = 0; i < ne; i++ ) nb[en[i][0]][en[i][1]] = '.';
		for ( i = 0; i < ne; i++ ) {
			int r = en2[i][0], c = en2[i][1];
			if ( nb[r][c] == '.' ) nb[r][c] = 'E';
			else if ( nb[r][c] == 'E' ) nb[r][c] = '#';
		}
		ne2 = 0;
		for ( i = 0; i < ne; i++ ) {
			int r = en2[i][0], c = en2[i][1];
			if ( nb[r][c] == 'E' ) {
				en2[ne2][0] = r;
				en2[ne2++][1] = c;
			}
		}
		if ( Try(d + 1, nr, nc, nb, en2, ne2) ) return 1;
	}
	return 0;
}

void
Solve(int rs, int cs, int en[][2], int ne)
{
	if ( Try(0, rs, cs, board, en, ne) ) printf("I'm the king of the Seven Seas!\n");
	else printf("Oh no! I'm a dead man!\n");
}

int
main()
{
	int T;
	scanf("%d", &T);
	while ( T-- ) {
		int rs, cs;
		ne = 0;
		for ( int i = 0; i < row; i++ ) {
			scanf("%s", board[i]);
			for ( int j = 0; j < col; j++ ) 
				if ( board[i][j] == 'S' ) {
					rs = i; cs = j;
					board[i][j] = '.';
				} else if ( board[i][j] == 'E' ) {
					en[ne][0] = i;
					en[ne++][1] = j;
				}
		}
		Solve(rs, cs, en, ne);
	}
}