| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
WA成鬼了,求测试数据#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator