Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WA成鬼了,求测试数据

Posted by haipeng31 at 2011-06-16 20:40:53 on Problem 2965
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
using namespace std;

const int ALLOPEN = 0;
const int STATENUM = 0xffff;

struct State {
	int state;
	vector<int> svec;
};

int visited[STATENUM];
queue<State> state_queue;

void gen_init_state(State *init_state, string *chess_board) {
	
	int init_helper = 1;
	for (int i = 3; i >= 0; i--) {
		for (int j = 3; j >= 0; j--) {
			if (chess_board[i][j] == '+') {
				init_state->state ^= init_helper;
			}
			init_helper *= 2;
		}
	}
	
}

State flip_handle(State handle_state, int index) {
	int flip_helper[] = { 0xf888, 0xf444, 0xf222, 0xf111,
		                  0x8f88, 0x4f44, 0x2f22, 0x1f11,
						  0x88f8, 0x44f4, 0x22f2, 0x11f1,
						  0x888f, 0x444f, 0x222f, 0x111f };
	handle_state.state ^= flip_helper[index];
	handle_state.svec.push_back(index);
	return handle_state;
}

void print_rs(State rs_state) {
	cout << rs_state.svec.size() << endl;
	for (int i = 0; i < rs_state.svec.size() ; i++) {
		cout << rs_state.svec[i] / 4 + 1 << ends << rs_state.svec[i] % 4 + 1 << endl;
	}
}

void bfs(State init_state) {
	visited[init_state.state] = 1;
	state_queue.push(init_state);

	while (state_queue.size() != 0) {
		State temp = state_queue.front();
		state_queue.pop();

		for (int i = 0; i < 16; i++) {
			State rs_state = flip_handle(temp, i);
			if (rs_state.state == ALLOPEN) {
				print_rs(rs_state);
				return;
			}
			if (!visited[rs_state.state]) {
				visited[rs_state.state] = 1;
				state_queue.push(rs_state);
			}
		}
	}
}

int main()
{
	State init_state;
	string handle_board[4];
	memset(&init_state, 0, sizeof(init_state));
	memset(visited, 0, sizeof(visited));
	
	for (int i = 0; i < 4; i++) {
		cin >> handle_board[i];
	}
		
	gen_init_state(&init_state, handle_board);
	
	bfs(init_state);


	return 0;

}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator