pku2157.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <memory.h>
#define SIZE 22

typedef struct Pos
{
	int x, y;
} Pos;

Pos Q[500];
int M, N;
char map[SIZE][SIZE], v[SIZE][SIZE];
int key[5], key_sum, unopen[5];
const int F[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

int InMap(int x, int y)
{
    return x >= 0 && y >= 0 && x < M && y < N;
}

void OpenTheDoor(int id)
{
    int i, j;
    for (i = 0; i < M; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (map[i][j] == id + 'A')
                map[i][j] = '.';
        }
    }
}

/******************************************
*此函数返回值不小于零表示找到的钥匙的数量 
*返回-1表示找到了宝藏 
******************************************/
int floodfill()
{
    int head, tail;
    int i, nx, ny, x, y, find_key;
    memset(v, 0, sizeof(v));
    v[Q[0].x][Q[0].y] = 1;
    head = 0;
    tail = 1;
    find_key = 0;
    while (head < tail)
    {
        x = Q[head].x;
        y = Q[head].y;
        for (i = 0; i < 4; i++)
        {
            nx = x + F[i][0];
            ny = y + F[i][1];
            if (!InMap(nx, ny) || map[nx][ny] == 'X' || v[nx][ny])
                continue;
            if (map[nx][ny] >= 'A' && map[nx][ny] <= 'E')
                continue;
            if (map[nx][ny] >= 'a' && map[nx][ny] <= 'e')
            {
                key[map[nx][ny] - 'a']--;
                find_key++;
                map[nx][ny] = '.';
            }
            if (map[nx][ny] == 'G')
                return -1;
            Q[tail].x = nx;
            Q[tail].y = ny;
            v[nx][ny] = 1;
            tail++;
        }
        head++;
    }
    return find_key;
}

/*********************************
*此函数返回1表示可以达到
*返回0表示不可达到 
*********************************/
int Solve()
{
	int i, j, find_key;
	memset(key, 0, sizeof(key));
	memset(unopen, 0, sizeof(unopen));
	key_sum = 0;
	for (i = 0; i < M; i++)
	    scanf("%s", map[i]);
    for (i = 0; i < M; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (map[i][j] == 'S')
            {
                Q[0].x = i;
                Q[0].y = j;
            }
            else if (map[i][j] >= 'a' && map[i][j] <= 'e')
            {
                key[map[i][j] - 'a']++;
                key_sum++;
            }
            else if (map[i][j] >= 'A' && map[i][j] <= 'E')
            {
                unopen[map[i][j] - 'A'] = 1;
            }
        }
    }
    while (1)
    {
        find_key = floodfill();
        if (find_key == -1)
            return 1;
        key_sum -= find_key;
        if (find_key == 0)
            return 0;
        for (i = 0; i < 5; i++)
        {
			if (key[i] == 0 && unopen[i])
            {
                OpenTheDoor(i);
            }
        }
    }
}

int main()
{
	while (EOF != scanf("%d %d", &M, &N) && (M || N))
	    printf("%s\n", Solve() ? "YES" : "NO");
	return 0;
}