本文主要是介绍UVA 10085 - The most distant state，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=110&page=show_problem&problem=1026
类型： 隐式图搜索
原题：
The 8-puzzle is a square tray in which eight square tiles are placed. The remaining ninth square is uncovered. Each tile has a number on it. A tile that is adjacent to the blank space can be slid into that space. A game consists of a starting state and a specified goal state. The starting state can be transformed into the goal state by sliding (moving) the tiles around. The 8-puzzle problem asks you to do the transformation in minimum number of moves.
| 2 | 8 | 3 |
|
|
| 1 | 2 | 3 |
| 1 | 6 | 4 | => | 8 |
| 4 | ||
| 7 |
| 5 |
|
|
| 7 | 6 | 5 |
| Start |
|
|
| Goal | ||||
However, our current problem is a bit different. In this problem, given an initial state of the puzzle your are asked to discover a goal state which is the most distant (in terms of number of moves) of all the states reachable from the given state.
Input
The first line of the input file contains an integer representing the number of test cases to follow. A blank line follows this line.
Each test case consists of 3 lines of 3 integers each representing the initial state of the puzzle. The blank space is represented by a 0 (zero). A blank line follows each test case.
Output
For each test case first output the puzzle number. The next 3 lines will contain 3 integers each representing one of the most distant states reachable from the given state. The next line will contain the shortest sequence of moves that will transform the given state to that state. The move is actually the movement of the blank space represented by four directions : U (Up), L (Left), D (Down) and R (Right). After each test case output an empty line.
Sample Input
12 6 4
1 3 7
0 5 8
Sample Output
Puzzle #18 1 5
7 3 6
4 0 2
UURDDRULLURRDLLDRRULULDDRUULDDR
题目大意：
题目都说了是八数码问题，不同的是，这个不是求一个八数码初始状态到达目标状态的最少步数， 而是要随便走，找出走的步数最多的那个状态，不能重复。
分析与总结：
解题过程与标准八数码问题基本相似， 不同的是，这个没有一个目标状态，所以要让它尽情地搜索，搜啊搜，一直到无法再搜下去了，那么最终状态就是步数最多的那个状态。在搜的过程记录下路径再输出即可。
// Time: 0.744s (UVA)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define MAXN 1000000
using namespace std;
char input[30];
int state[9], goal[9] = {1,2,3,8,0,4,7,6,5};
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上，下，左， 右
char path_dir[5] = "UDLR";
int st[MAXN][9];
int father[MAXN], path[MAXN], ans; // 保存打印路径const int MAXHASHSIZE = 1000003;
int head[MAXHASHSIZE], next[MAXN];void init_lookup_table() { memset(head, 0, sizeof(head)); }typedef int State[9];
int hash(State& s) {int v = 0;for(int i = 0; i < 9; i++) v = v * 10 + s[i];return v % MAXHASHSIZE;}int try_to_insert(int s) {int h = hash(st[s]);int u = head[h];while(u) {if(memcmp(st[u], st[s], sizeof(st[s])) == 0) return 0;u = next[u];}next[s] = head[h];head[h] = s;return 1;
}void bfs(){init_lookup_table();father[0] = path[0] = -1;int front=0, rear=1;memcpy(st[0], state, sizeof(state));try_to_insert(0);while(front < rear){int *s = st[front];int j;for(j=0; j<9; ++j) if(!s[j])break; // 找出0的位置int x=j/3, y=j%3; // 转换成行，列for(int i=0; i<4; ++i){int dx = x+dir[i][0]; // 新状态的行，列int dy = y+dir[i][1];int pos = dx*3+dy; // 目标的位置if(dx>=0 && dx<3 && dy>=0 && dy<3){int *newState = st[rear];memcpy(newState, s, sizeof(int)*9);newState[j] = s[pos];newState[pos] = 0;if(try_to_insert(rear)){father[rear] = front; path[rear] = i;rear++;}}} front++;}ans = rear-1;
}void print_path(int cur){if(cur!=0){print_path(father[cur]);printf("%c", path_dir[path[cur]]);}
}int main(){int T, cas=1;scanf("%d", &T);while(T--){for(int i=0; i<9; ++i){scanf("%d", &state[i]);}bfs();printf("Puzzle #%d\n", cas++);for(int i=0; i<3; ++i){printf("%d %d %d\n", st[ans][i*3], st[ans][i*3+1], st[ans][i*3+2]);}print_path(ans);printf("\n\n");}
}
—— 生命的意义，在于赋予它意义。
这篇关于UVA 10085 - The most distant state的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
