原题链接：https://vjudge.net/problem/UVA-810 分类：图 备注：思维,DFS
要注意判重,在原图基础上加两个维度：筛子的top和front即可，否则可能陷入死循环。 还有注意，本题看筛子的方向是从上向下看的，因此你在电脑前的右边才是题目中的左边。
代码如下：
#include<iostream> #include<cstring> #include<string> #include<vector> #include<queue> using namespace std; const int base = 100; const int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; string name; int R, C, sr, sc, g[15][15], val[7][7]; int vis[15][15][7][7]; struct node { int top, front; void update(int pos) { if (pos == 0) {//向下滚 int tmp = 7 - front; front = top; top = tmp; } else if (pos == 1) {//向上滚 int tmp = 7 - top; top = front; front = tmp; } else if (pos == 2) //向右滚 top = 7 - val[front][top]; else //向左滚 top = val[front][top]; } }; bool ok = false; vector<int>ansX, ansY; void dfs(node head) { int nr = ansX.back(); int nc = ansY.back(); for (int i = 0; i < 4; i++) { int row = nr + dir[i][0]; int col = nc + dir[i][1]; if (row<1 || col<1 || row>R || col>C)continue; if (g[row][col] != -1 && head.top != g[row][col])continue; if (g[row][col] == -1) { if (ansX.size() >= 2) { int pos = ansX.size() - 2; if (ansX[pos] == row && ansY[pos] == col)continue; } } node u = head; u.update(i); if (vis[row][col][u.top][u.front])continue; vis[row][col][u.top][u.front] = 1; ansX.push_back(row); ansY.push_back(col); if (row == sr && col == sc) { ok = true; return; } dfs(u); if (!ok) { ansX.pop_back(); ansY.pop_back(); } else return; } } int main(void) { //val[front][top]左边的数字 val[1][2] = 4; val[1][3] = 2, val[1][4] = 5, val[1][5] = 3; val[2][1] = 3; val[2][3] = 6, val[2][4] = 1, val[2][6] = 4; val[3][1] = 5; val[3][2] = 1; val[3][5] = 6; val[3][6] = 2; val[4][1] = 2; val[4][2] = 6; val[4][5] = 1; val[4][6] = 5; val[5][1] = 4; val[5][3] = 1; val[5][4] = 6; val[5][6] = 3; val[6][2] = 3; val[6][3] = 5; val[6][4] = 2; val[6][5] = 4; while (cin >> name) { if (name == "END")break; memset(vis, 0, sizeof(vis)); ansX.clear(); ansY.clear(); ok = false; cin >> R >> C >> sr >> sc; node head; cin >> head.top >> head.front; ansX.push_back(sr); ansY.push_back(sc); for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) cin >> g[i][j]; dfs(head); cout << name << endl; if (ok) { for (int i = 0, num = 0; i < ansX.size(); i++) { if (!num)cout << " "; cout << "(" << ansX[i] << "," << ansY[i] << ")"; if (i != ansX.size() - 1)cout << ","; num++; if (num == 9) { num = 0; cout << endl; } } if (ansX.size() % 9)cout << endl; } else cout << " No Solution Possible" << endl; } return 0; }