1054: [HAOI2008]移动玩具

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1272  Solved: 690

[Submit][Status][Discuss]

Description

在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

Input

前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。

Output

一个整数,所需要的最少移动次数。

Sample Input

1111 0000 1110 0010 1010 0101 1010 0101

Sample Output

4

HINT

Source

题解:其实是一道水水哒搜索题,只要你知道怎么状压,怎么用一个数组判重同时记录最优值就好了

(PS:其实我WA掉的那一次是没特判开头结尾情况完全一样的情形,应该输出0,而我原来的程序将没有输出= =,注意下)

  1 /**************************************************************
  2     Problem: 1054
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:36 ms
  7     Memory:772 kb
  8 ****************************************************************/
  9  
 10 var
 11    i,j,k,l,m,n,x0,x1,x,y,f,r:longint;
 12    c,d:array[0..70000] of longint;
 13    list:array[0..20] of longint;ch:char;
 14 function num(x,y:longint):longint;inline;
 15          begin
 16               exit(4*(x-1)+y);
 17          end;
 18 function getit(x,y:longint):longint;inline;
 19          begin
 20               if odd(x div list[y]) then exit(1) else exit(0);
 21          end;
 22 procedure orz(x:longint);inline;
 23           begin
 24                writeln(x);
 25                readln;
 26                halt;
 27           end;
 28 begin
 29      list[1]:=1;for i:=2 to 16 do list[i]:=list[i-1]*2;
 30      x0:=0;x1:=0;
 31      for i:=1 to 4 do
 32          begin
 33               for j:=1 to  4 do
 34                   begin
 35                        read(ch);
 36                        inc(x0,(ord(ch)-48)*list[num(i,j)]);
 37                   end;
 38               readln;
 39          end;
 40      readln;
 41      for i:=1 to 4 do
 42          begin
 43               for j:=1 to  4 do
 44                   begin
 45                        read(ch);
 46                        inc(x1,(ord(ch)-48)*list[num(i,j)]);
 47                   end;
 48               readln;
 49          end;
 50      if x0=x1 then orz(0);
 51      for i:=0 to 65536 do c[i]:=maxlongint;
 52      d[1]:=x0;f:=1;r:=2;c[x0]:=0;
 53      while f<r do
 54            begin
 55                 l:=d[f];i:=1;x:=1;y:=0;
 56                 while l>0 do
 57                       begin
 58                            x:=x+y div 4;y:=y mod 4+1;
 59                            if odd(l) then
 60                               begin
 61                                    if x>1 then
 62                                       begin
 63                                            if getit(d[f],i-4)=0 then
 64                                               begin
 65                                                    d[r]:=d[f]-list[i]+list[i-4];
 66                                                    if c[d[r]]=maxlongint then
 67                                                       begin
 68                                                            c[d[r]]:=c[d[f]]+1;
 69                                                            if d[r]=x1 then orz(c[d[r]]);
 70                                                            inc(r);
 71                                                       end;
 72                                               end
 73                                       end;
 74                                    if x<4 then
 75                                       begin
 76                                            if getit(d[f],i+4)=0 then
 77                                               begin
 78                                                    d[r]:=d[f]-list[i]+list[i+4];
 79                                                    if c[d[r]]=maxlongint then
 80                                                       begin
 81                                                            c[d[r]]:=c[d[f]]+1;
 82                                                            if d[r]=x1 then orz(c[d[r]]);
 83                                                            inc(r);
 84                                                       end;
 85                                               end;
 86                                       end;
 87                                    if y>1 then
 88                                       begin
 89                                            if getit(d[f],i-1)=0 then
 90                                               begin
 91                                                    d[r]:=d[f]-list[i]+list[i-1];
 92                                                    if c[d[r]]=maxlongint then
 93                                                       begin
 94                                                            c[d[r]]:=c[d[f]]+1;
 95                                                            if d[r]=x1 then orz(c[d[r]]);
 96                                                            inc(r);
 97                                                       end;
 98                                               end;
 99                                       end;
100                                    if y<4 then
101                                       begin
102                                            if getit(d[f],i+1)=0 then
103                                               begin
104                                                    d[r]:=d[f]-list[i]+list[i+1];
105                                                    if c[d[r]]=maxlongint then
106                                                       begin
107                                                            c[d[r]]:=c[d[f]]+1;
108                                                            if d[r]=x1 then orz(c[d[r]]);
109                                                            inc(r);
110                                                       end;
111                                               end;
112                                       end;
113                               end;
114                            inc(i);l:=l div 2;
115                       end;
116                 inc(f);
117            end;
118 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣学算法

数据结构 第10讲 好玩贪吃蛇——数字矩阵

1003
来自专栏AI研习社

用在数据科学上的 Python:你可能忘记的 8 个概念

如果你在编程的时候发现自己一遍又一遍的搜索同一个问题、概念或者语法,那么你并不孤单。

961
来自专栏desperate633

LeetCode 213. House Robber II题目分析代码方法二

在上次打劫完一条街道之后,窃贼又发现了一个新的可以打劫的地方,但这次所有的房子围成了一个圈,这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额...

732
来自专栏数说工作室

统计师的Python日记【第八天:数据清洗(2)文本处理】

本文是【统计师的Python日记】第8天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数、...

6726
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构之线性表

正文之前 ? 昨天晚上阶段性的完成了一部分数学的复习(一元积分学终于搞定了,后面的貌似没这么难了),所以今天打算撸一撸代码,结合前几天写的链表实现线性存储,今天...

3756
来自专栏C语言及其他语言

【每日一题】尼科彻斯定理

题目描述 验证尼科彻斯定理,即:任何一个正整数的立方都可以写成一串连续奇数的和。 输入 任一正整数 输出 该数的立方分解为一串连续奇数的和 样例输入 13 样例...

3319
来自专栏养码场

趣读 | 怎样算是「风骚」的代码?

关于Unlambda语言,David Madore是这个语言的发明人,他于1976年8月3日生于法国,其是法国-加拿大籍数学家和计算机科学爱好者)。在unlam...

852
来自专栏数说工作室

庖丁解牛切割数据!| 【SAS Says·扩展篇】

【SAS Says·扩展篇】庖丁解牛割数据! | 3. call PRXSUBSTR () 0. 前集回顾 1. 新的问题 2. 初识 PRXSUBSTR() ...

3326
来自专栏大数据挖掘DT机器学习

[笔记]使用Python一步一步地来进行数据分析

原文 http://www.cnblogs.com/nxld/p/6058998.html 你已经决定来学习Python,但是你之前没有编程经验。因此,你常常...

7136
来自专栏专知

不只是支持Windows, PyTorch 0.4新版本变动详解与升级指南

6062

扫码关注云+社区

领取腾讯云代金券