题目链接:
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
1
2 6 4
1 3 7
0 5 8
Sample Output
Puzzle #1
8 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");
}
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
利用腔的输入和输出过程产生基于氮空缺中心的GHZ态纠缠,郑安寿,吕新友,本文提出了一种替代方案实现N量子比特的氮空位中心分布在不同的光子晶体纳腔的GHZ态纠缠,该方案的实现是基于光子的输入和输出过程�
Mon-depot-distant
DISTANT
When it comes to texts, one of the most common fixed-length features is bag-of-words. Despite their popularity, bag-of-words features have two major weaknesses: they lose the ordering of the words ...
Distant supervision 相关文献 Distant supervision 相关文献
Java 项目说明, 简单的例子能够说明如果列举项目类别
Hopefully I will be able to attend your seminar in the not-too-distant future. Randall R. Hawley, Automation Technician, Eli Lilly & Co. The best computer book writing I have seen. Tom Holland
Distant galaxy
Deep Ranking Based Cost-sensitive Multi-label Learning for Distant Supervision Relation Extraction
Two problems arise when using distant su- pervision for relation extraction. First, in this method, an already existing knowl- edge base is heuristically aligned to texts, and the alignment results ...
To realize the auto-calibration, we first use the distant lighting model to estimate the initial surface albedo map, and then with the estimated albedo map and the normal vector field fixed, the ...
Hamiltonian dynamics can be used to produce distant proposals for the Metropolis algorithm, thereby avoiding the slow exploration of the state space that results from the diffusive behaviour of simple...
代码片段: <h1 class='dilate'>Dilate ...<h1 class='distant-top'>Distant Top <h1 class='distant-front'>Distant Front <h1 class='diff1'>Diffused Light <h1 class='bevel'>Bevel</h1>
entrepot-distant:Unentrepot遥远
A scheme is proposed to implement quantum state transfer between two distant atoms through sending the atoms across two distant cavities connected via an optical fiber. The field state, which ...
In the mysterious and limitless space, performed in a different schedule, you'll see a distant galaxy surrounded by planetary systems and nebulas. Discovery 3D Screensaver v1.1 build 5 Get ready ...
-identify identify the format and characteristics of the image -ift implements the inverse discrete Fourier transform (DFT) -implode amount implode image pixels about the center -lat geometry ...
噪音鲁棒的神经网络关系抽取模型,姜廷松,穗志方,关系抽取的目标是从文本中自动抽取实体间关系,远程监督能够自动标注训练数据,使得关系抽取可以面向大规模语料展开。远程监督面临�
Distant Supervised Relation Extraction with Cost-Sensitive Loss
遥远的贝斯版权所有(c)2019-2021 该存储库包含distant-bes的代码,一个用于将构建结果注入实现服务的库。安装为了安装该库,请克隆此存储库并运行pip install distant-bes/ 。兼容性该库已经针对构建事件协议的...