A Dicey Problem UVA - 810

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<deque>
using namespace std;

int dir[4][2] = {-1,0,1,0,0,-1,0,1};//上下左右
int Right[10][10];//前面、顶面---->右面
int R, C, stax, stay, Top, Face;
int visit[15][15][10][10];
int area[15][15];
vector<int> result;

struct node{
	int x, y, Top, Face, pre, index;
	node(int a = 0, int b = 0, int t = 0, int f = 0, int in = -1, int p = -1){
		x = a; y = b; Top = t; Face = f; index = in; pre = p;
	}
};

void overturn(int& t,int& f,int d){
	if (d == 0){//上
		int temp = t;
		t = f;
		f = 7 - temp;
	}
	else if (d == 1){//下
		int temp = f;
		f = t;
		t = 7 - temp;
	}
	else if (d == 2){//左
		t = Right[f][t];
	}
	else{//d==3,右
		t = 7 - Right[f][t];
	}
}

void getResult(int ind,node q[]){
	if (ind == -1) return;
	getResult(q[ind].pre,q);
	result.push_back(ind);
}

void BFS(){
	node q[20000];
	int head = 0, rear = 0;
	q[rear] = node(stax,stay,Top,Face,0,-1);
	rear++;
	while (head < rear){
		node temp = q[head];
		head++;
		for (int i = 0; i < 4; i++){
			int newx, newy;
			newx = temp.x + dir[i][0];
			newy = temp.y + dir[i][1];
			if (!(newx >= 1 && newx <= R&&newy >= 1 && newy <= C)) continue;
			if (area[newx][newy] != -1 && temp.Top != area[newx][newy]) continue;
			if (newx == stax&&newy == stay){
				getResult(temp.index, q);
				cout << "  ";
				for (int j = 0; j < result.size();){
					int ind = result[j];
					cout << "(" << q[ind].x << "," << q[ind].y << ")";
					j++;
					if (j % 9 == 0&&j!=0) cout << ",n  ";
					else cout << ",";
				}
				cout << "(" << newx << "," << newy << ")" << endl;
				return;
			}
			node temp2 = temp;
			temp2.x = newx; temp2.y = newy;
			overturn(temp2.Top, temp2.Face, i);
			if (visit[temp2.x][temp2.y][temp2.Top][temp2.Face]) continue;
			visit[temp2.x][temp2.y][temp2.Top][temp2.Face] = 1;
			temp2.index = rear;
			temp2.pre = temp.index;
			q[rear] = temp2;
			rear++;
		}
	}
	cout << "  No Solution Possible" << endl;
}

int main(){

	string name;
	Right[1][2] = 4; Right[1][3] = 2; Right[1][5] = 3; Right[1][4] = 5;
	Right[2][1] = 3; Right[2][4] = 1; Right[2][6] = 4; Right[2][3] = 6;
	Right[3][1] = 5; Right[3][2] = 1; Right[3][6] = 2; Right[3][5] = 6;
	Right[4][1] = 2; Right[4][5] = 1; Right[4][6] = 5; Right[4][2] = 6;
	Right[5][6] = 3; Right[5][4] = 6; Right[5][1] = 4; Right[5][3] = 1;
	Right[6][2] = 3; Right[6][4] = 2; Right[6][5] = 4; Right[6][3] = 5;
	while (cin >> name){
		result.clear();
		if (name == "END") break;
		cin >> R >> C >> stax >> stay >> Top >> Face;
		memset(visit,0,sizeof(visit));
		memset(area,0,sizeof(area));
		for (int i = 1; i <= R; i++){
			for (int j = 1; j <= C; j++){
				cin >> area[i][j];
			}
		}
		cout << name << endl;
		BFS();
	}
	return 0;
}