HDU 1430 关系映射 + 打表 ....

时间：2023-11-07 09:37:01 jhs200t电阻器 jhs保电阻电缆

意思是中文不解释.(http://acm.hdu.edu.cn/showproblem.php?pid=1430)

思路:

这个话题是直接的BFS会加班(我一开始加班) ,若考虑双向BFS感觉字典序那个地方控制不好，双向BFS也很费时间，其实我们可以打表，只跑一边BFS,以起点

从1、2、3、4、5、6、7、8开始，一直遍历所有状态，答案存在map至于里面map,

还是map一切都可以，只要正确hash就行了，看还有用"康拓公式"哈希的

(个人说没学过)，这样一边广搜后，就会得到一个从12345678开始到任何状态的答案，

下面是关键,每次会给我们一组数据,初始状态 s 和末状态 e ,我们应该找到将主题给出的数据与我们的表数据联系起来的方法，从而设计一个映射关系.

比如:

测试数据是 S 1 2 3 4 到 4 3 2 1

7 8 6 5 8 6 5 7

转换成 S 1 2 3 4 到 4 3 2 1

8 7 6 5 7 6 5 8

事实上，这是八个数字之间的位置关系。以测试数据的位置关系为规则，以1为规则 2 3 4 5 6 7 8

将此规则转换为相应的终点，然后直接输出打表后的答案OK了.

ac代码:

#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct
{
int now[2][4];
string road;
}NODE;
maphash;
queueq;
NODE xin ,tou;
bool jhs(NODE a)
{
int temp = 1 ,sum = 0;
for(int i = 0 ;i < 2 ;i )
for(int j = 0 ;j < 4 ;j )
{
sum = temp * a.now[i][j];
temp *= 10;
}
if(hash[sum] != "") return 1;
hash[sum] = a.road;
return 0;
}
void DB_BFS()
{
int temp = 0;
for(int i = 0 ;i < 4 ;i )
xin.now[0][i] = temp;
for(int i = 3 ;i >= 0 ;i --)
xin.now[1][i] = temp;
xin.road = "";
hash.clear();
jhs(xin);
while(!q.empty())
q.pop();
q.push(xin);
int i ,j;
while(!q.empty())
{
tou = q.front();
q.pop();
for(i = 0 ;i < 2 ;i )
for(j = 0 ;j < 4 ;j )
{
if(!i) xin.now[1][j] = tou.now[i][j];
else xin.now[0][j] = tou.now[i][j];
}
xin.road = tou.road 'A';
if(!jhs(xin))
{
q.push(xin);
}
for(i = 0 ;i < 2 ;i )
for(j = 1 ;j < 4 ;j )
xin.now[i][j] = tou.now[i][j-1];
xin.now[0][0] = tou.now[0][3];
xin.now[1][0] = tou.now[1][3];
xin.road = tou.road 'B';
if(!jhs(xin))
{
q.push(xin);
}
xin = tou;
xin.now[0][1] = tou.now[1][1];
xin.now[0][2] = tou.now[0][1];
xin.now[1][2] = tou.now[0][2];
xin.now[1][1] = tou.now[1][2];
xin.road = tou.road 'C';
if(!jhs(xin))
{
q.push(xin);
}
}
}
int main ()
{
char str1[20] ,str2[20];
int i ,j;
&bsp; int X[20];
DB_BFS();
while(~scanf("%s%s" ,str1 ,str2))
{
int temp = 0;
for(i = 0 ;i < 4 ;i ++)
X[str1[i] - 48] = ++ temp;
for(i = 3 ;i >= 0 ;i --)
X[str1[7 - i] - 48] = ++ temp;
temp = 0;
int tt = 1 ,sum = 0;
for(i = 0 ;i < 4 ;i ++)
{
sum += X[str2[i] - 48] * tt;
tt *= 10;
}
for(i = 7 ;i >= 4 ;i --)
{
sum += X[str2[i] - 48] * tt;
tt *= 10;
}
if(hash[sum] == "AA")
puts("");
else
cout< }
return 0;
}

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

HDU 1430 关系映射 + 打表 ....

相关文章