1399.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1399 on 2006-01-20 at 16:09:34 */ 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int R_MAX = 32;
const int INTRO_MAX = 16;
const int IR_MAX = INTRO_MAX - 1;
const int S_MAX = 1 << IR_MAX;
const int INF = 2000000000;
const char *INSTR[] = { "AND", "OR", "XOR", "NOT", "MOV", "SET", 
												"RANDOM", "JMP", "JZ", "STOP", "NOP" };
enum { AND, OR, XOR, NOT, MOV, SET, RANDOM, JMP, JZ, STOP, NOP };
const int INTRO_ARG[] = { 2, 2, 2, 1, 2, 2, 1, 1, 2, 0, 0 };
const bool RELATE[11] = { true, true, true, false, true };
typedef pair<int, int> pii;

int ho[R_MAX], hn;
bool vst[INTRO_MAX*S_MAX], hinge[R_MAX];

class Intro {
public:
	int in, arg[2];
	void make();
	void update();
};
void Intro::make() {
	char order[8]; int i;
	scanf("%s", order);
	for(in = 0; strcmp(order, INSTR[in]); in++) ;
	for(i = 0; i < INTRO_ARG[in]; i++) scanf("%d", &arg[i]);
}
void Intro::update() {
	int i; bool nop = true;
	for(i = 0; i < INTRO_ARG[in]; i++)
		if((i == 0 && in != JMP && in != JZ) || (i == 1 && in != SET))
			if(hinge[arg[i]]) nop = false, arg[i] = ho[arg[i]];
	if(nop && in != STOP && in != JMP) in = NOP;
}

Intro intro[INTRO_MAX];

int BFS();
inline void push(queue<pii>&, int, int, int);

int main()
{
	int t, T, i, j, n;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		memset(hinge, false, sizeof(hinge));
		for(i = 0; i < n; i++) intro[i].make();
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(intro[j].in == JZ) hinge[intro[j].arg[1]] = true;
				else if(RELATE[intro[j].in] && hinge[intro[j].arg[0]])
					hinge[intro[j].arg[1]] = true;
		for(i = hn = 0; i < R_MAX; i++)
			if(hinge[i]) ho[i] = hn++;
		for(i = 0; i < n; i++) intro[i].update();
		int r = BFS();
		if(r == INF) printf("HANGS\n");
		else printf("%d\n", r+1);
	}
	
	return 0;
}

int BFS()
{
	int i, d;
	if(hn == 0) {
		for(i = d = 0; intro[i].in != STOP; d++)
			if(intro[i].in == NOP) i++;
			else if(intro[i].arg[0] <= i) return INF;
			else i = intro[i].arg[0];
		return d;
	} else {
		queue<pii> Q;
		memset(vst, false, sizeof(vst));
		while(!Q.empty()) Q.pop();
		for(i = 0; i < (1<<hn); i++) Q.push(pii(i, 0)), vst[i] = true;
		while(!Q.empty()) {
			pii t = Q.front(); Q.pop();
			int reg = t.first & 32767, o = t.first >> 15;
			int arg0 = intro[o].arg[0], arg1 = intro[o].arg[1], in = intro[o].in;
			switch(in) {
			case AND:
				if((reg & (1<<arg1)) == 0) reg &= ~(1<<arg0);
				push(Q, o+1, reg, t.second);
			break;
			case OR:
				reg |= ((reg>>arg1)&1) << arg0;
				push(Q, o+1, reg, t.second);
			break;
			case XOR:
				reg ^= ((reg>>arg1)&1) << arg0;
				push(Q, o+1, reg, t.second);
			break;
			case NOT:
				reg ^= 1 << arg0;
				push(Q, o+1, reg, t.second);
			break;
			case MOV: arg1 = (reg&(1 << arg1)) >> arg1;
			case SET:
				if(arg1 == 1) reg |= 1 << arg0;
				else reg &= ~(1<<arg0);
				push(Q, o+1, reg, t.second);
			break;
			case RANDOM:
				reg &= ~(1<<arg0);
				push(Q, o+1, reg, t.second);
				push(Q, o+1, reg|(1<<arg0), t.second);
			break;
			case JZ: if(reg & (1<<arg1)) arg0 = o+1;
			case JMP: push(Q, arg0, reg, t.second); break;
			case NOP: push(Q, o+1, reg, t.second); break;
			case STOP: return t.second;
			}
		}
		
		return INF;
	}
}
inline void push(queue<pii>& Q, int p, int s, int step)
{
	int m = (p<<15) | s;
	if(!vst[m]) Q.push(pii(m, step+1)), vst[m] = true;
}