HDU 3567 Eight II
Eight II
This problem will be judged on HDU. Original ID: 3567
64-bit integer IO format: %I64d Java class name: Main
In this game, you are given a 3 by 3 board and 8 tiles. The tiles are numbered from 1 to 8 and each covers a grid. As you see, there is a blank grid which can be represented as an 'X'. Tiles in grids having a common edge with the blank grid can be moved into that blank grid. This operation leads to an exchange of 'X' with one tile.
We use the symbol 'r' to represent exchanging 'X' with the tile on its right side, and 'l' for the left side, 'u' for the one above it, 'd' for the one below it.
A state of the board can be represented by a string S using the rule showed below.
The problem is to operate an operation list of 'r', 'u', 'l', 'd' to turn the state of the board from state A to state B. You are required to find the result which meets the following constrains:
1. It is of minimum length among all possible solutions.
2. It is the lexicographically smallest one of all solutions of minimum length.
Input
The input of each test case consists of two lines with state A occupying the first line and state B on the second line.
It is guaranteed that there is an available solution from state A to B.
Output
The first line is in the format of "Case x: d", in which x is the case number counted from one, d is the minimum length of operation list you need to turn A to B.
S is the operation list meeting the constraints and it should be showed on the second line.
Sample Input
2
12X453786
12345678X
564178X23
7568X4123
Sample Output
Case 1: 2
dd
Case 2: 8
urrulldr
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
struct sta{
int x,y;
sta(int a = ,int b = ){
x = a;
y = b;
}
};
char mp[maxn][maxn];
sta s[];
int nowx,nowy;
int h(){
int tmp = ;
for(int i = ; i < ; i++){
int x = i/,y = i%;
if(mp[x][y] == 'X') continue;
tmp += abs(x - s[mp[x][y]-''].x) + abs(y - s[mp[x][y]-''].y);
}
return tmp;
}
int ans[],limit;
const int dir[][] = {,,,-,,,-,};
const char d[] = {'d','l','r','u'};
bool ok;
int IDAstar(int x,int y,int p,int cur){
int bound = INF,tmp;
int hv = h();
if(cur + hv > limit) return cur + hv;
if(hv == ) {ok = true;return cur;}
for(int i = ; i < ; i++){
if(i == p) continue;
int tx = x + dir[i][];
int ty = y + dir[i][];
if(tx < || tx >= || ty < || ty >= ) continue;
swap(mp[x][y],mp[tx][ty]);
ans[cur] = i;
int nbound = IDAstar(tx,ty,-i,cur+);
if(ok) return nbound;
bound = min(bound,nbound);
swap(mp[x][y],mp[tx][ty]);
}
return bound;
}
int main() {
int t,cs = ;
char ch;
scanf("%d",&t);
getchar();
while(t--){
for(int i = ; i < ; i++){
ch = getchar();
if(ch == 'X'){
nowx = i/;
nowy = i%;
}
mp[i/][i%] = ch;
}
getchar();
for(int i = ; i < ; i++){
ch = getchar();
if(ch == 'X') continue;
s[ch-''] = sta(i/,i%);
}
getchar();
limit = h();
ok = false;
while(!ok) limit = IDAstar(nowx,nowy,-,);
printf("Case %d: %d\n",cs++,limit);
for(int i = ; i < limit; i++)
putchar(d[ans[i]]);
putchar('\n');
}
return ;
}
最新文章
- JAVA+Maven+TestNG搭建接口测试框架及实例
- 程序员的成长与规划 | 送签名书啦 | StuQ专访foruok
- LINUX 配置IP
- MS-queue算法相关
- 惊叹jQuery(解决jQuery对象到DOM的转换)
- 剑指Offer43 n个骰子点数概率
- Failure [INSTALL_FAILED_OLDER_SDK]
- ABP入门系列(16)——通过webapi与系统进行交互
- Maven项目pom.xml 标签含义
- JS显示动态的系统时间--JavaScript基础
- 机器学习之决策树二-C4.5原理与代码实现
- 前端(一)之 HTML
- Karen and Game CodeForces - 816C (暴力+构造)
- 使用 sizeof 获取字符串数组的大小
- Orleans学习总结(一)--入门认识
- 移动app传统测试流程优化
- jQuery的ajax跨域 Jsonp原理
- 2.vo传参模式和ModerDriven传参模式
- [C++] 用Xcode来写C++程序[4] 函数
- Oracle Inventory Management Application Program Interface ( APIs) (Doc ID 729998.1)
热门文章
- Odoo(OpenERP)开发实践:数据模型学习
- Codeforces Round #200 (Div. 2)D. Alternating Current (堆栈)
- android 构建GPS Provide步骤及信息
- Windows 10家庭版也能共享打印机(中)解除Guest账户网络登录限制,实现局域网共享
- bzoj5194: [Usaco2018 Feb]Snow Boots
- PowerShell攻防进阶篇:nishang工具用法详解
- php模版静态化原理
- Gym-101915B Ali and Wi-Fi 计算几何 求两圆交点
- Nginx实现负载均衡 + Keepalived实现Nginx的高可用
- Hadoop MapReduce编程 API入门系列之join(二十六)(未完)