/*
*******************************************************************************
*
* Filename: 10021.cpp
*
* Description:
*
* Version: 0.1
* Created: 4/27/2009 8:11:22 AM
*
* Author: Ye Xiaofeng , yexfeng # gmail.com
*
*******************************************************************************
*/
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
/*
* +------+
* / UP /|
* +------+ |
* |FRONT |R+ -----------------
* | |/ board
* +------+ -----------------
*/
#define FRONT 0
#define BACK 1
#define UP 2
#define DOWN 3
#define LEFT 4
#define RIGHT 5
__inline void roll_left(short* cube);
__inline void roll_right(short* cube);
__inline void roll_up(short* cube);
__inline void roll_down(short* cube);
short cube_start[6] = { 1, 2, 3, 4, 5, 6 };
struct Pos {
int x;
int y;
bool operator==(Pos& pos)
{
if (this->x == pos.x && this->y == pos.y) {
return true;
}
return false;
}
};
struct Node {
bool operator==(Node& node)
{
if (pos == node.pos && 0 == memcmp(node.cube, cube, 6*sizeof(short))) {
return true;
}
return false;
}
short cube[6];
Pos pos;
unsigned int prev_node;
};
struct Cell {
Cell();
vector<unsigned int> used_node;
//
// 0: no wall
// 1: down wall
// 2: right wall
// 3: down and right wall
//
short wall;
};
struct Case {
Case();
int search_move_num();
bool find_used_node(Node& node);
void insert_used_node(Pos& pos, unsigned int index);
void show_path(Node& node);
vector<Node> node_list;
int row;
int col;
Pos start;
Pos end;
vector< vector<Cell> > board;
bool showflg;
};
int Case::search_move_num()
{
vector<unsigned int> expand_list;
int move_count = 0;
Node first_node;
first_node.pos = start;
first_node.prev_node = 0xffffffff;
memcpy(first_node.cube, cube_start, 6*sizeof(short));
node_list.push_back(first_node);
insert_used_node(first_node.pos, 0);
expand_list.push_back(node_list.size()-1);
while (expand_list.size() != 0) {
vector<unsigned int> tmp_node_list;
move_count++;
for (int i = 0; i < expand_list.size(); i++) {
Node cur_expand_node = node_list[expand_list[i]];
bool expand = true;
if (cur_expand_node.pos.x == 8 && cur_expand_node.pos.y == 0) {
show_path(cur_expand_node);
}
// move left
if (cur_expand_node.pos.y > 0 && !(board[cur_expand_node.pos.x][cur_expand_node.pos.y-1].wall & 0x02)) {
if (cur_expand_node.prev_node != -1) {
Node prev_node = node_list[cur_expand_node.prev_node];
if (prev_node.pos.y == cur_expand_node.pos.y-1 && prev_node.pos.x == cur_expand_node.pos.x) {
expand = false;
}
}
if (expand) {
Node tmp_node = cur_expand_node;
tmp_node.pos.y--;
roll_left(tmp_node.cube);
tmp_node.prev_node = expand_list[i];
if (tmp_node.pos == end && tmp_node.cube[DOWN] == cube_start[DOWN]) {
cout << move_count << endl;
return move_count;
}
if (!find_used_node(tmp_node)) {
node_list.push_back(tmp_node);
tmp_node_list.push_back(node_list.size()-1);
insert_used_node(tmp_node.pos, node_list.size()-1);
}
}
}
expand = true;
// move right
if (cur_expand_node.pos.y < col-1 && !(board[cur_expand_node.pos.x][cur_expand_node.pos.y].wall & 0x02)) {
if (cur_expand_node.prev_node != -1) {
Node prev_node = node_list[cur_expand_node.prev_node];
if (prev_node.pos.y == cur_expand_node.pos.y+1 && prev_node.pos.x == cur_expand_node.pos.x) {
expand = false;
}
}
if (expand) {
Node tmp_node = cur_expand_node;
tmp_node.pos.y++;
roll_right(tmp_node.cube);
tmp_node.prev_node = expand_list[i];
if (tmp_node.pos == end && tmp_node.cube[DOWN] == cube_start[DOWN]) {
cout << move_count << endl;
return move_count;
}
if (!find_used_node(tmp_node)) {
node_list.push_back(tmp_node);
tmp_node_list.push_back(node_list.size()-1);
insert_used_node(tmp_node.pos, node_list.size()-1);
}
}
}
// move up
expand = true;
if (cur_expand_node.pos.x > 0 && !(board[cur_expand_node.pos.x-1][cur_expand_node.pos.y].wall & 0x01)) {
if (cur_expand_node.prev_node != -1) {
Node prev_node = node_list[cur_expand_node.prev_node];
if (prev_node.pos.y == cur_expand_node.pos.y && prev_node.pos.x == cur_expand_node.pos.x-1) {
expand = false;
}
}
if (expand) {
Node tmp_node = cur_expand_node;
tmp_node.pos.x--;
roll_up(tmp_node.cube);
tmp_node.prev_node = expand_list[i];
if (tmp_node.pos == end && tmp_node.cube[DOWN] == cube_start[DOWN]) {
cout << move_count << endl;
return move_count;
}
if (!find_used_node(tmp_node)) {
node_list.push_back(tmp_node);
tmp_node_list.push_back(node_list.size()-1);
insert_used_node(tmp_node.pos, node_list.size()-1);
}
}
}
// move down
expand = true;
if (cur_expand_node.pos.x < row-1 && !(board[cur_expand_node.pos.x][cur_expand_node.pos.y].wall & 0x01)) {
if (cur_expand_node.prev_node != -1) {
Node prev_node = node_list[cur_expand_node.prev_node];
if (prev_node.pos.y == cur_expand_node.pos.y && prev_node.pos.x == cur_expand_node.pos.x+1) {
expand = false;
}
}
if (expand) {
Node tmp_node = cur_expand_node;
tmp_node.pos.x++;
roll_down(tmp_node.cube);
tmp_node.prev_node = expand_list[i];
if (tmp_node.pos == end && tmp_node.cube[DOWN] == cube_start[DOWN]) {
cout << move_count << endl;
return move_count;
}
if (!find_used_node(tmp_node)) {
node_list.push_back(tmp_node);
tmp_node_list.push_back(node_list.size()-1);
insert_used_node(tmp_node.pos, node_list.size()-1);
}
}
}
}
expand_list = tmp_node_list;
}
cout << "No solution" << endl;
return 0;
}
int main(int argc, char **argv)
{
int case_num = 0;
Case cs;
char line_buffer[10] = "";
cin >> case_num;
for (; case_num > 0; case_num--) {
// input board size
cs.node_list.clear();
cin >> cs.row >> cs.col;
cs.board = vector< vector<Cell> >(cs.row, vector<Cell>(cs.col, Cell()));
cin >> cs.start.x >> cs.start.y;
cin >> cs.end.x >> cs.end.y;
cs.start.x--;
cs.start.y--;
cs.end.x--;
cs.end.y--;
char wall_type = ' ';
Pos wall_pos;
cin.getline(line_buffer, 10);
while (1) {
cin.getline(line_buffer, 10);
if (cin.eof() || line_buffer[0] == '\0') {
break;
}
if (line_buffer[0] == 'v' || line_buffer[0] == 'h') {
wall_type = line_buffer[0];
continue;
} else {
stringstream ss;
ss << line_buffer;
ss >> wall_pos.x >> wall_pos.y;
wall_pos.x--;
wall_pos.y--;
switch (wall_type) {
case 'v':
cs.board[wall_pos.x][wall_pos.y].wall |= 0x01;
break;
case 'h':
cs.board[wall_pos.x][wall_pos.y].wall |= 0x02;
break;
default:
cout << "Wrong input" << endl;
exit(1);
}
}
}
cs.search_move_num();
if (case_num != 1) {
cout << endl;
}
}
}
__inline void roll_left(short* cube)
{
short old_left = cube[LEFT];
cube[LEFT] = cube[UP];
cube[UP] = cube[RIGHT];
cube[RIGHT] = cube[DOWN];
cube[DOWN] = old_left;
}
__inline void roll_right(short* cube)
{
short old_left = cube[LEFT];
cube[LEFT] = cube[DOWN];
cube[DOWN] = cube[RIGHT];
cube[RIGHT] = cube[UP];
cube[UP] = old_left;
}
__inline void roll_up(short* cube)
{
short old_up = cube[UP];
cube[UP] = cube[FRONT];
cube[FRONT] = cube[DOWN];
cube[DOWN] = cube[BACK];
cube[BACK] = old_up;
}
__inline void roll_down(short* cube)
{
short old_up = cube[UP];
cube[UP] = cube[BACK];
cube[BACK] = cube[DOWN];
cube[DOWN] = cube[FRONT];
cube[FRONT] = old_up;
}
Case::Case()
{
row = 0;
col = 0;
showflg = false;
}
Cell::Cell()
{
wall = 0;
}
bool Case::find_used_node(Node& node)
{
Cell cell = board[node.pos.x][node.pos.y];
for (int i = 0; i < cell.used_node.size(); i++) {
if (node == node_list[cell.used_node[i]]) {
return true;
}
}
return false;
}
void Case::insert_used_node(Pos& pos, unsigned int index)
{
board[pos.x][pos.y].used_node.push_back(index);
}
void Case::show_path(Node& node)
{
if (showflg) {
cout << '(' << node.pos.x << ',' << node.pos.y << ')' << '\t';
for (int i = 0; i < 6; i++) {
cout << node.cube[i];
}
cout << endl;
unsigned int prev = node.prev_node;
cout << '(' << node.pos.x << ',' << node.pos.y << ')' << endl;
while (prev != 0xffffffff) {
Node prev_node = node_list[prev];
cout << '(' << prev_node.pos.x << ',' << prev_node.pos.y << ')' << '\t';
for (int i = 0; i < 6; i++) {
cout << prev_node.cube[i];
}
cout << endl;
prev = prev_node.prev_node;
}
cout << endl;
}
}
|
