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