贪吃蛇

题目：

http://oj.changjun.com.cn/problem/detail/pid/2185

Description

身长为L的贪吃蛇在一个有障碍的N*M的格子中游走，问最少用多少步才能让贪吃蛇的蛇头到达(1，1）。

Input

第一行三个正整数 N, M，L。L表示贪吃蛇的长度。
接下来 L 行，顺序描述贪吃蛇每节身体的位置。每行两个正整数 X，Y。表示某节身体的位置，按蛇头到蛇尾的顺序描述。
接下来一个正整数K。表示有 K个障碍，每个障碍占一个格子。
接下来K行，每行两个正整数 X，Y，表示某个障碍的位置。

Output

一个整数，表示到达格子（1,1）最少的步数。（给定数据保证能够到达，并且蛇头移动的目标格子必须是空的。）

Sample Input

Sample Output

9

Hint

对于 100% 的数据，2≤N、M≤20，2≤L≤8

解析：

可以广搜，但状态懒得存，干脆写个迭代加深搜索，代码简洁好写。

可是迭代深搜复杂度还是比较高的，我们考虑ＩＤＡ＊。

先预处理出每个点到终点的距离，记为dis[x][y]。

记当前层数为now，迭代层数为deep。

当dis[x][y]+now>deep时，则return;因为怎么都不可能在deep-now步之内走到终点。

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 using namespace std;
15 int n,m;
16 int q1[1000],q2[1000],head=1,tail=0;
17 int mp[25][25],fb[25][25],w[5]={0,1,-1,0,0},u[5]={0,0,0,1,-1};
18 int vis[25][25],dis[25][25];
19 int ww[5]={0,0,0,1,-1},uu[5]={0,1,-1,0,0};
20 void DFS(int deep,int now)
21 {
22   int xx=q1[tail],yy=q2[tail];
23   if(now+dis[xx][yy]>deep) return;//IDA*
24   if(now==deep){
25     if(xx==1 && yy==1) printf("%d",deep),exit(0);
26     else return;
27   }
28   for(int i=1;i<=4;i++)
29     {
30       int x=xx+w[i],y=yy+u[i];
31       if(x>0 && x<=n && y>0 && y<=m && !mp[x][y]){
32     mp[x][y]=1;
33     q1[++tail]=x,q2[tail]=y;
34     int kx=q1[head],ky=q2[head];
35     mp[kx][ky]=0;head++;
36     DFS(deep,now+1);
37     mp[kx][ky]=1;
38     mp[x][y]=0;
39     head--;tail--;
40       }
41     }
42 }
43 void BFS()
44 {
45   queue<int>q1,q2;
46   q1.push(1),q2.push(1);
47   vis[1][1]=1;
48   while(!q1.empty()){
49     int xx=q1.front(),yy=q2.front();
50     q1.pop();q2.pop();
51     for(int i=1;i<=4;i++)
52       {
53     int x=xx+ww[i],y=yy+uu[i];
54     if(x>0 && x<=n && y>0 && y<=n && !fb[x][y] && !vis[x][y])
55       dis[x][y]=dis[xx][yy]+1,q1.push(x),q2.push(y),vis[x][y]=1;
56       }
57   }
58 }
59 int main()
60 {
61   freopen("snake.in","r",stdin);
62   freopen("snake.out","w",stdout);
63   int L,x,y,k;
64   scanf("%d%d%d",&n,&m,&L);
65   for(int i=1;i<=L;i++){
66     scanf("%d%d",&x,&y);
67     q1[L-i+1]=x;q2[L-i+1]=y;
68     mp[x][y]=1;
69   }
70   scanf("%d",&k);
71   for(int i=1;i<=k;i++)
72     scanf("%d%d",&x,&y),mp[x][y]=1,fb[x][y]=1;
73   BFS();
74   for(int i=0;i<=n;i++)
75     for(int j=0;j<=m;j++)
76       fb[i][j]=mp[i][j];
77   for(int i=0;;i++)
78     {
79       head=1;tail=L;
80       DFS(i,0);
81       for(int j=0;j<=n;j++)
82     for(int ij=0;ij<=m;ij++)
83       mp[j][ij]=fb[j][ij];
84     }
85 }