2073.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2073 on 2006-01-22 at 00:02:07 */ 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int MAX = 32;
const int AIM = 0;

class Door {
public:
	int dn, next[MAX], lock[MAX], o;
	void open(Door&, const int);
	bool unlock(const int, const int) const;
};
void Door::open(Door& d, int need) {
	next[dn] = d.o; d.next[d.dn] = o; 
	lock[dn++] = d.lock[d.dn++] = need;
}
bool Door::unlock(const int key, const int lo) const {
	return (key & lock[lo]) == lock[lo];
}

int main()
{
	Door door[MAX];
	int get[MAX], begin, n, i, j;
	char info[16], ch;
	bool vst[MAX];

	for(i = 0; i < MAX; i++) door[i].o = i;
	while(scanf("%s", info) != EOF && strcmp(info, "ENDOFINPUT")) {
		scanf("%d %d", &begin, &n); getchar();
		for(i = 0; i < n; i++) door[i].dn = 0;
		for(i = 0; i < n; i++)
			while(true) {
				while((ch = getchar()) == ' ');
				if(ch == '\n') break;
				else {
					ungetc(ch, stdin);
					int next, lock = 0; scanf("%d", &next);
					while(isalpha(ch = getchar())) lock |= 1 << (ch-'A');
					door[i].open(door[next], lock);
					ungetc(ch, stdin);
				}
			}
		memset(get, 0, sizeof(get));
		for(i = 0; i < n; i++)
			while((ch = getchar()) != '\n')
				if(isalpha(ch)) get[i] |= 1 << (ch-'A');
		bool improve = true; int key = get[begin]; 
		memset(vst, false, sizeof(vst)); vst[begin] = true;
		while(improve && !vst[AIM]) {
			improve = false;
			for(i = 0; i < n; i++)
				for(j = 0; vst[i] && j < door[i].dn; j++) {
					int k = door[i].next[j];
					if(!vst[k] && door[i].unlock(key, j)) {
						improve = vst[k] = true;
						key |= get[k];
					}
				}
		}
		printf("%s\n", vst[AIM] ? "YES" : "NO");
		gets(info);
	}

	return 0;
}