POJ3221 Diamond Puzzle(BFS:最短路)
http://poj.org/problem?id=3221
题意:如下的平面魔方,现在给你一个魔方的初态,比如3图,要你算出从3图移动到2图的状态需要多少步。其中每步移动只能交换空格(0那格)与它相邻的格子的内容。
分析:首先我们要想好怎么表示一个状态,我们用一个人char s[10]来表示状态,比如2图的状态是0123456.
然后我们用BFS扩展队列中节点的后续状态,并且计算到新状态的最短距离。但是这里我们还需要判断新状态以前是否出现过,所以我们用hash表来判重,其实与前几道题目基本是一样的思路,不过就是改了下数据形式。hash表我们可以自己实现,也可以直接用STL中的map<string,int>hash来表示。
注意:由于题目有很多组数组,所以我们事先求出从0123456到所有可能状态的距离,然后对于题目的每个询问输出即可。(否则超时)
本题我用的是STL中的map来作为hash查重,且用的STL中的queue,没有自己写hash和队列,代码短了(正常情况下本题应该在100行代码以上,但是下面只写了60几行),速度也不慢,关键错误少了,直接一次AC。STL中的东西在一定情况下还是推荐使用的。
AC代码:
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
#include<queue>
using namespace std;
const int maxn=10000;
int d[7][5]={{2,4,6,-1},{2,6,-1},{0,1,3,-1},{2,4,-1},{0,3,5,-1},{4,6,-1},{0,1,5,-1}};
//d[i][j]=x 表示原始标记的i格能与原始标记的x格交换
map<string ,int> vis;//判断当前状态是否出现过,map中的int初值为0,也即如果对应string不存在,那么就是int为0值
map<string ,int> ans;//当前状态出现的最小操作步数
struct Node
{
char s[10];//保存状态
int dist;//最小步数
};
queue<Node> Q;
char s[10]="0123456";
void BFS()
{
Node node1;
strcpy(node1.s,s);
node1.dist=0;
Q.push(node1);
ans[string(s)]=0;
vis[string(s)]=1;
while(!Q.empty())
{
Node node=Q.front();Q.pop();
int pos;//pos表状态中0的位置
for(int i=0;node.s[i];i++)if(node.s[i]=='0') {pos=i; break;}
for(int i=0;d[pos][i]!=-1;i++)//依次遍历当前0位置能交换的对应位置
{
int npos=d[pos][i];//pos能交换的对应位置为npos
Node node2= node;
node2.s[pos]=node.s[npos];
node2.s[npos]=node.s[pos];
node2.dist =1+node.dist;
if(vis[string(node2.s)]==0)//此状态之前未出现过
{
vis[string(node2.s)]=1;
ans[string(node2.s)]=node2.dist;
Q.push(node2);
}
}
}
}
int main()
{
BFS();
int T; scanf("%d",&T);
while(T--)
{
char str[10];
scanf("%s",str);
if(strcmp(str,s)==0) printf("0\n");
else printf("%d\n",ans[string(str)]==0?-1:ans[string(str)]);
}
return 0;
}
分享到:
相关推荐
poj 3388 Japanese Puzzle.md
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
北大POJ初级题-数据结构:解题报告+AC代码
poj还是leetcode ProgrammingCompetionCareer 大学的竞赛生涯结束了,抽时间整理了一部分曾经在OJ刷过的题,还有一些找不到了,或者是因为杂物太多(除了代码以外还有题解的pdf、题目的测试数据等等),不想整理了就...
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj1002 source code input: The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on ...
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
poj与leetcode
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj 2893 M × N Puzzle.md
poj 3131 Cubic Eight-Puzzle.md
poj 5346题,四则运算表达式求值的实现,用栈和队列实现中缀转后缀后计算,含解题报告与源码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_mark: 数据结构 串 POJ 1016 POJ 1035 POJ ...
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看