HDU 2605 Snake（DFS+BFS+技巧+细节）（好题）

缺乏、安全感 2022-06-15 12:25 127阅读 0赞

<table style="font-family:'Times New Roman'; word-wrap:break-word"> 
 <tbody> 
  <tr> 
   <td align="center"> <h1 style="color:rgb(26,92,200)">Snake</h1> <strong><span style="font-family:Arial; color:green">Time Limit: 10000/6000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others)<br> Total Submission(s): 222&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 45</span></strong><br> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Problem Description 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      Snake is a popular game , and I believe most of us had played it . The Original game is that you can control a snake to eat the magic bean and after the snake eat one magic bean , the length of the snake’s body will get longer .But today we are talking about a new game. These are the rules of the new Snake Game : 
     <br> 1. The length of the snake’s body won’t change even though it eat a magic bean. 
     <br> 2. Some pairs of the beans have a relation , that is, one of them can not be eaten until another one had been eaten . We call the latter “the key bean” . For example , if A can’t be eaten until B had been eaten ,we say “B is the key bean of A”. (That means when A can’t be eaten , the snake can not move into the grid where A is.) 
     <br> 3. The snake could not move to a wall or its body.Befor it move,it will chooses an adjacent vacant square of its head,which is neither a stone nor occupied by its body. 
     <br>  Figure 1 and figure2 shows how the snake move  
     <br>  
     <img src="http://acm.hdu.edu.cn/data/images/C154-1006-1.jpg" alt="" style="border:none; max-width:100%">  
     <br>  Figure 1  
     <br>  
     <img src="http://acm.hdu.edu.cn/data/images/C154-1006-2.jpg" alt="" style="border:none; max-width:100%">  
     <br>  Figure 2  
    </div> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      The first line contain a integer T (T &lt;= 10).Followed by T cases. Each case contain five parts. 
     <br> The first part: six integers ,H,W,L,K,R,N,(H &lt;= 20 , W &lt;= 20 , L &lt;= 8 , K &lt;= 7 ) means the height of the map , the width of the map , the length of the snake’s body, the number of the magic beans . the number of the relations , the number of the wall respectively. 
     <br> The second part: L lines , each line contain two integer h 
     <sub>i</sub>&nbsp;,w 
     <sub>i</sub>, indicating the original position of each block of snake's body, from B 
     <sub>1</sub>(h 
     <sub>1</sub>,w 
     <sub>1</sub>) to B 
     <sub>L</sub>(h 
     <sub>L</sub>,w 
     <sub>L</sub>) orderly, where 1&lt;=h 
     <sub>i</sub>&lt;=H, and 1&lt;=w 
     <sub>i</sub>&lt;=W,1&lt;=i&lt;=L. 
     <br> The third part: K lines ,each line contain two integer h 
     <sub>i</sub>&nbsp;,w 
     <sub>i</sub>&nbsp;, indicating the position of each magic bean , from MB 
     <sub>1</sub>(h 
     <sub>1</sub>,w 
     <sub>1</sub>) to MB 
     <sub>K</sub>(h 
     <sub>K</sub>,w 
     <sub>K</sub>) orderly, where 1&lt;=h 
     <sub>i</sub>&lt;=H, and 1&lt;=w 
     <sub>i</sub>&lt;=W,1&lt;=i&lt;=K. 
     <br> The fourth part : R lines , each line contain two integer A ,B means “A is the key bean of B ”. The A and B may appear several times , but “one bean will have only one key bean”. 
     <br> The fifth part: N lines , each line contain two integer h 
     <sub>i</sub>&nbsp;,w 
     <sub>i</sub>&nbsp;, indicating the position of each wall , from W 
     <sub>1</sub>(h 
     <sub>1</sub>,w 
     <sub>1</sub>) to W 
     <sub>N</sub>(h 
     <sub>N</sub>,w 
     <sub>N</sub>) orderly, where 1&lt;=h 
     <sub>i</sub>&lt;=H, and 1&lt;=w 
     <sub>i</sub>&lt;=W,1&lt;=i&lt;=N. 
     <span style="font-family:Arial,Helvetica,sans-serif; font-size:12px">&nbsp;</span> 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      For each case , if the snake could eat all the magic beans , output the minimum step it took. If the snake could not , just output “-1” (without the quotation marks) . 
     <br> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">      
       
      <div style="font-family:'Courier New',Courier,monospace">
       
        
       1
8 9
5 2
1 8
5 2
6 2
6 3
6 4
6 5
4 2
2 6
2 1
2 5
3 5
4 4
4 5
4 6
5 6
5 7
6 7
      
       
      </div></pre> 
    </div> 
    <div style="height:auto; margin:0px"> 
     <br> 
    </div> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">      
       
      <div style="font-family:'Courier New',Courier,monospace">
       
        
       21
      
       
      </div></pre> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Author 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      Teddy 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Source 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left"> 
     <a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=HDU+1st+%A1%B0Vegetable-Birds+Cup%A1%B1+Programming+Open+Contest&amp;source=1&amp;searchmode=source" style="color:rgb(26,92,200); text-decoration:none" rel="nofollow">HDU 1st “Vegetable-Birds Cup” Programming Open Contest</a> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

题目链接：

[点击打开链接][Link 1]

题解：

这是个好题啊。贪食蛇。爆搜。

注意一下一些细节和技巧就可以。

可能需要你花很多时间慢慢写....

反正我写了一个晚上....

很考验自己的的代码能力，我写了7K...300+行...

注意：

豆子也要成环...dfs判断一下即可。

然后再BFS，判断是否越界或者撞墙，还要判断豆子能不能吃。还要判断蛇头不能碰到自己。

注意MLE，利用一下位运算就可以了。用bitset大法应该也是可以的。