算法专题训练搜索a-T3 Ni骑士(ni)

　　搞了半天八数码弄不出来就只好来打题解这道题是在搜索a碰到的(链接: http://pan.baidu.com/s/1jG9rQsQ ) 感觉题目最大亮点就是这英文简写"ni", 真是令人感慨出题老师的才华啊好了，废话不多说题目内容如下（闲烦请无视之，下下方有简单的介绍):

【问题描述】
贝西（Bessie）在卡摩洛遇到了棘手的情况：她必须穿越由Ni骑士把守的森林。骑士答应Bessie
只要 Bessie 能给他们带来一丛灌木就能安全穿越森林。时间宝贵，Bessie 必须尽快找到一丛灌木
然后给骑士送去。
Bessie有一张森林的地图。森林被划分成了W×H个网格（1≤W≤1000; 1≤H≤1000）。每个
网格用0～4的整数表示。

0：可以通行；
1：无法通行（沼泽、悬崖、杀手）；
2：Bessie的起始位置；
3：骑士的起始位置；
4：灌木丛。
Bessie 只能朝上下左右四个方向行走，每走一个网格要花一天的时间，请超出一条到达骑士的
最短路。问题保证有解。
【输入】
输入文件的第一行是W和H；
一般来讲，后面有 H 行每行 W 个整数（即 0～4），表示地图。但是当某行的整数个数超过 40 个
时，就会另起一行。
【输出】
输出Bessie至少需要几天才能把灌木丛带给骑士。

【输入样例】
8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0
【输出样例】
11
【Hint】
Explanation of the sample:

Width=8, height=4. Bessie starts on the third row, only a few squares away from the Knights.
Bessie can move in this pattern to get a shrubbery for the Knights: N, W, N, S, E, E, N, E, E, S, S. She gets the
shrubbery in the northwest corner and then makes her away around the barriers to the east and then south to
the Knights.

　　题目内容一大堆,说简单点就是给出一张W*H（1<=W,H<=1000）的地图，每个位置都标有0..4的数字。其中0表示可以通过，1表示不能通过，2表示Bessie的起始位置，3表示骑士起始位置，4表示树丛。现在要求求出一条最短的路，使骑士经过树丛至少一次，且能够到达Bessie所在位置。

　　一开始看到题目认为这个好简单啊不就是一个裸的bfs吗于是就开始打了第一遍代码打了之后发现思路很混乱往哪儿开始搜索都搞不清于是再看题目这一看就明白了就是题中的单精度小女孩(......)要去找它的骑士大哥（666......)当然，这位小女孩还要经过一个树丛柑橘（这不是废话吗)

　　这给人第一感觉就是从树丛开始往girl和boy搜素用一个s数组保存到某个点的最小距离一开始值设置成0 然后从第一个树开始一个个搜过去每搜一次保存最小值也就是s[a1][b1]+s[a2][b2](a1,b1,a2,b2分别是girl和boy的坐标位置当然这里也需要注意一下如果没有搜到的话 bfs也是会退出的这样的话相应s数组的值也可能还是0 这里就要加一个特判也就是当两个s的值都不等于0时才进行（一开始答案输出老是0 看到这里把数据输出来才知道被坑了所以说数组返回值有风险（适当的宾语前置。），使用需谨慎。

好像又讲开了，那么我们还是回归正题。(啊，正题是什么......) 好，这样几遍的bfs之后样例就能正确输出了（好高兴啊）过程代码如下：

 1 void bfs(int a,int b)
 2 {
 3     s[a][b]=1;
 4     q[1].push(a);
 5     q[2].push(b);
 6     q[3].push(0);
 7     while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
 8     {
 9         for(int d=1;d<=4;d++)
10         {
11             int x=q[1].front()+dx[d];
12             int y=q[2].front()+dy[d];
13             if(g[x][y]==1||x<1||x>h||y<1||y>w)
14                 continue;
15             if(s[x][y]==0)
16             {
17                 s[x][y]=q[3].front()+1;
18 //              cout<<"x "<<x<<' '<<"y "<<y<<endl;
19 //              cout<<"s   "<<s[x][y]<<endl;
20                  sum2++; 
21                 q[1].push(x);
22                 q[2].push(y);
23                 q[3].push(s[x][y]);
24                 if(s[a1][b1]>0&&s[a2][b2]>0)
25                 {
26 //                  cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
27                     return;
28                 }
29             }
30         }
31         q[1].pop();
32         q[2].pop();
33         q[3].pop();
34     }
35 }

　　然后去测只过了8个点（很郁闷这难道不是bfs吗再看看数据100w 应该能过嘛）但再看我这里的不止是一次bfs 而是对于每个草丛都要来一次bfs 复杂度就由此极大的提高了有没有办法剪枝呢?

　　于是我会教室又去想终于在眼保健操的时候有了一点灵感：既然问题的一方面出在对于每个树都搜过去而造成了某种意义上的超时那么我们是不是可以在这里加个条件以减少bfs的次数呢? 如果当前搜的书与起点终点的曼哈顿距离已经比minn大了那么

无论怎么走都不可能了和以前做的一道售货员的难题的剪枝像然后，看到了教室前面开着的电脑内心想着：反正才第一节嘛还有时间于是我就飞奔地上去测了果然原来6s跑出来的第九个点这次只要1.3s了呵呵，然后记得那节晚读整个人都好了

可是，1.3s只是较以前的6s有了一些较大的改进但还远远不够

　　那么，再接着想：既然我在bfs的做之前加了这么一个条件那么在bfs内部拓展节点的时候是不是也可以试着加个类似的条件呢? 仔细想想bfs的“原理” 它是从近往远的每一排节点进行拓展的也就是说下一次取队头出来的肯定是要比这次大的好那么在有了理论依据和现实基础后我果断的在进行是否拓展过的判断之前加了这样一个条件

问题似乎迎刃而解了再去测第九个点终于闯入了1s大关 0.7! 再怀着兴奋的心情去搞第十个点时答案却也再没有显示出来了 (好忧伤......)

　　于是我又再想假如他数据前面几次的minn是很大但又递减的呢这样的话我在bfs前的判断不久跟没做过一样嘛 WTF! 但转念一想数据是死的但人是活的嘛于是我就想干脆对每个树枝对于其道起点终点的曼哈顿距离进行排序如下图所示：

　　然后终于第十个点在教室0.7s跑出来了!!!!! （记得我后来高兴了一节历史课）然后去机房测 0.3 好了，这道题就在机房终于a掉了

　　顺便发表一下我的感慨：真的感觉最后把这题做出来很有成就感每一次改进都是一次小的跃进 oi或许正是需要这种不懈的探索精神吧

　　难道故事就这样结束了吗?(Q:有的人认为这句话也可以去掉但也有人说不可以去掉你认为呢? A:这句话承上启下起到了过渡的作用同时亦吸引了读者的阅读兴趣 (666...))

　　好讲到这里我便先把前面的ac代码放出来给大家看看 (由于配置不够在家测要1s+ 请勿见怪本文最后亦会提及一种更好的方法）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cstring>
  5 #include<ctime>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<cstring>
  9 using namespace std;
 10 const int maxn=750+10;
 11 struct node
 12 {
 13     int x,y;
 14 }data[maxn];
 15 int g[maxn][maxn],s[maxn][maxn];
 16 int dx[5]={0,1,0,-1,0};
 17 int dy[5]={0,0,1,0,-1};
 18 int w,h,cnt=0,sum1=0,sum2=0;
 19 int a1,b1,a2,b2,k1;
 20 int s1,s2,minn=0x7f7f7f;
 21 queue<int>q[4];
 22 int distance1(int a,int b)
 23 {
 24     return (abs(a1-a)+abs(a2-a)+abs(b1-b)+abs(b2-b));
 25 }
 26 void bfs(int a,int b)
 27 {
 28     sum1++;
 29 //  queue<int>q[4];
 30     s[a][b]=1;
 31     q[1].push(a);
 32     q[2].push(b);
 33     q[3].push(0);
 34     while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
 35     {
 36         for(int d=1;d<=4;d++)
 37         {
 38             int x=q[1].front()+dx[d];
 39             int y=q[2].front()+dy[d];
 40             if(g[x][y]==1||x<1||x>h||y<1||y>w)
 41                 continue;
 42             if(distance1(x,y)>minn)
 43                     continue;
 44             if(s[x][y]==0)
 45             {
 46                 s[x][y]=q[3].front()+1;
 47 //              cout<<"x "<<x<<' '<<"y "<<y<<endl;
 48 //              cout<<"s   "<<s[x][y]<<endl;
 49                  sum2++; 
 50                 q[1].push(x);
 51                 q[2].push(y);
 52                 q[3].push(s[x][y]);
 53                 if(s[a1][b1]>0&&s[a2][b2]>0)
 54                 {
 55 //                  cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
 56                     return;
 57                 }
 58             }
 59         }
 60         q[1].pop();
 61         q[2].pop();
 62         q[3].pop();
 63     }
 64 }
 65 bool my_comp(node a,node b)
 66 {
 67     return (distance1(a.x,a.y)<distance1(b.x,b.y));
 68 }
 69 int main()
 70 {
 71     ios::sync_with_stdio(false);
 72 //    freopen("ni.in","r",stdin);
 73 //    freopen("ni.out","w",stdout);
 74     freopen("1.in","r",stdin);
 75 //    freopen("1.out","w",stdout);
 76     cin>>w>>h;
 77     for(int i=1;i<=h;i++)
 78         for(int j=1;j<=w;j++)
 79         {
 80             cin>>g[i][j];
 81             if(g[i][j]==2)
 82             {
 83                 a1=i;
 84                 b1=j;
 85             }
 86             if(g[i][j]==3)
 87             {
 88                 a2=i;
 89                 b2=j;
 90             }
 91             if(g[i][j]==4)
 92             {
 93                 k1++;
 94                 data[k1].x=i;
 95                 data[k1].y=j;
 96             }
 97         }
 98 //  for(int i=1;i<=h;i++)
 99 //  {
100 //      for(int j=1;j<=w;j++)
101 //          cout<<g[i][j]<<' ';
102 //      cout<<endl;
103 //  }
104 //      cout<<g[2][1]<<endl;
105 //      cout<<g[2][1]<<endl;
106 //  for(int i=1;i<=h;i++)
107 //      for(int j=1;j<=w;j++)
108 //          if(g[i][j]==4)
109             sort(data+1,data+k1+1,my_comp);
110             for(int i=1;i<=k1;i++)
111             {
112                 if(distance1(data[i].x,data[i].y)>minn)
113                     continue;
114                 while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
115                 {
116                     if(!q[1].empty())
117                         q[1].pop();
118                     if(!q[2].empty())
119                         q[2].pop();
120                     if(!q[3].empty())
121                         q[3].pop();
122                 }
123 //              cout<<i<<' '<<j<<endl;
124 //              while(!q[1].empty())
125 //                  q[1].pop();
126 //              while(!q[2].empty())
127 //                  q[2].pop();
128 //              while(!q[3].empty())
129 //                  q[3].pop();
130                 
131                 memset(s,0,sizeof(s));
132                 bfs(data[i].x,data[i].y);
133 //              cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
134                 if(s[a1][b1]!=0&&s[a2][b2]!=0&&s[a1][b1]+s[a2][b2]<minn)
135                     minn=s[a1][b1]+s[a2][b2];
136             }
137  //           cout<<sum1<<' '<<sum2<<endl; 
138     cout<<minn<<endl;
139 //    cout << "
" << (double)clock() / CLOCKS_PER_SEC;
140  //     cout<<sum<<endl; 
141     return 0;
142 }

　　好了，以上是我的代码做完后我又去问了一下yyl学长又获得了一些启示：

　　1.这道题用手工队列比STL里的要来的快突出表现在不需要用一个while 一遍遍的弹队列直接改一下head和tail 就行了

　　2.事实上我在改进之后的bfs次数减少了很多(453次bfs，515269次拓展）但事实上并不需要这么多次bfs 只需要从起点和终点开始统计出每个树丛到起点和终点的最少步数最后对每个树丛统计就好了

　　3.山外有山，码外有码或许换种方式算法会有更大的改进

　　另外，至于最后yyl学长提出的改进我将会尽量在明天给出代码现在真的太困了得先睡觉了

　　好了，起床，开更

　　对于上面说的方法我刚刚又再敲了一遍从girl和boy出发全图遍历至所有的树丛都找到为止在这里需要一个判断由于才疏学浅我就直接线性遍历数组了　　

　　对了还有一点就是代码中的bfs过程中可以直接引用数组的参数但我弄了半天都不行(*s ? s[ ]) 于是我就直接重新copy了一遍过程(弱弱的气息......)

　但实际上可以用hash 康托展开等方法来实现之这些的话等我以后有时间再把代码补上吧家里电脑(配置很烂,当年机房0.2s的家里跑了3s)勉强1s能过如右图所示：

代码如下：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cstring>
  5 #include<ctime>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<cstring>
  9 using namespace std;
 10 const int maxn=750+10;
 11 struct node
 12 {
 13     int x,y;
 14 }data[maxn];
 15 int g[maxn][maxn],s1[760][760],s2[760][760];
 16 int dx[5]={0,1,0,-1,0};
 17 int dy[5]={0,0,1,0,-1};
 18 int w,h,cnt=0,sum1=0,sum2=0;
 19 int a1,b1,a2,b2,k1,k2;
 20 int minn=0x7f7f7f;
 21 queue<int>q[4];
 22 int distance1(int a,int b)
 23 {
 24     return (abs(a1-a)+abs(a2-a)+abs(b1-b)+abs(b2-b));
 25 }
 26 bool all1()
 27 {
 28     for(int i=1;i<=k1;i++)
 29         if(s1[data[i].x][data[i].y]==0)
 30             return false;
 31     return true;
 32 }
 33 bool all2()
 34 {
 35     for(int i=1;i<=k1;i++)
 36         if(s2[data[i].x][data[i].y]==0)
 37             return false;
 38     return true;
 39 }
 40 void bfs1(int a,int b)
 41 {
 42 //    sum1++;
 43 //  queue<int>q[4];
 44     s1[a][b]=1;
 45     q[1].push(a);
 46     q[2].push(b);
 47     q[3].push(0);
 48     while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
 49     {
 50         for(int d=1;d<=4;d++)
 51         {
 52             int x=q[1].front()+dx[d];
 53             int y=q[2].front()+dy[d];
 54             if(g[x][y]==1||x<1||x>h||y<1||y>w)
 55                 continue;
 56 //            if(distance1(x,y)>minn)
 57 //                    continue;
 58             if(s1[x][y]==0)
 59             {
 60                 s1[x][y]=q[3].front()+1;
 61 //              cout<<"x "<<x<<' '<<"y "<<y<<endl;
 62 //              cout<<"s   "<<s[x][y]<<endl;
 63 //                 sum2++; 
 64                 q[1].push(x);
 65                 q[2].push(y);
 66                 q[3].push(s1[x][y]);
 67                 if(all1())
 68                 {
 69 //                  cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
 70                     return;
 71                 }
 72             }
 73         }
 74         q[1].pop();
 75         q[2].pop();
 76         q[3].pop();
 77     }
 78 }
 79 void bfs2(int a,int b)
 80 {
 81 //    sum1++;
 82 //  queue<int>q[4];
 83     s2[a][b]=1;
 84     q[1].push(a);
 85     q[2].push(b);
 86     q[3].push(0);
 87     while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
 88     {
 89         for(int d=1;d<=4;d++)
 90         {
 91             int x=q[1].front()+dx[d];
 92             int y=q[2].front()+dy[d];
 93             if(g[x][y]==1||x<1||x>h||y<1||y>w)
 94                 continue;
 95 //            if(distance1(x,y)>minn)
 96 //                    continue;
 97             if(s2[x][y]==0)
 98             {
 99                 s2[x][y]=q[3].front()+1;
100 //              cout<<"x "<<x<<' '<<"y "<<y<<endl;
101 //              cout<<"s   "<<s[x][y]<<endl;
102 //                 sum2++; 
103                 q[1].push(x);
104                 q[2].push(y);
105                 q[3].push(s2[x][y]);
106                 if(all2())
107                 {
108 //                  cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
109                     return;
110                 }
111             }
112         }
113         q[1].pop();
114         q[2].pop();
115         q[3].pop();
116     }
117 }
118 bool my_comp(node a,node b)
119 {
120     return (distance1(a.x,a.y)<distance1(b.x,b.y));
121 }
122 int main()
123 {
124     ios::sync_with_stdio(false);
125     freopen("ni.in","r",stdin);
126     freopen("ni.out","w",stdout);
127 //    freopen("1.in","r",stdin);
128 //    freopen("1.out","w",stdout);
129     cin>>w>>h;
130     for(int i=1;i<=h;i++)
131         for(int j=1;j<=w;j++)
132         {
133             cin>>g[i][j];
134             if(g[i][j]==2)
135             {
136                 a1=i;
137                 b1=j;
138             }
139             if(g[i][j]==3)
140             {
141                 a2=i;
142                 b2=j;
143             }
144             if(g[i][j]==4)
145             {
146                 k1++;
147                 data[k1].x=i;
148                 data[k1].y=j;
149             }
150         }
151         bfs1(a1,b1);
152         while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
153         {
154             if(!q[1].empty())
155                 q[1].pop();
156             if(!q[2].empty())
157                 q[2].pop();
158             if(!q[3].empty())
159                 q[3].pop();
160         }
161         bfs2(a2,b2);
162         for(int i=1;i<=k1;i++)
163         {
164             if(s1[data[i].x][data[i].y]!=0&&s2[data[i].x][data[i].y]!=0)
165                 minn=min(minn,s1[data[i].x][data[i].y]+s2[data[i].x][data[i].y]);
166         }
167         cout<<minn<<endl;
168 //  for(int i=1;i<=h;i++)
169 //  {
170 //      for(int j=1;j<=w;j++)
171 //          cout<<g[i][j]<<' ';
172 //      cout<<endl;
173 //  }
174 //      cout<<g[2][1]<<endl;
175 //      cout<<g[2][1]<<endl;
176 //  for(int i=1;i<=h;i++)
177 //      for(int j=1;j<=w;j++)
178 //          if(g[i][j]==4)
179 //            sort(data+1,data+k1+1,my_comp);
180 //            for(int i=1;i<=k1;i++)
181 //            {
182 //                if(distance1(data[i].x,data[i].y)>minn)
183 //                    continue;
184 //                while((!q[1].empty())&&(!q[2].empty())&&(!q[3].empty()))
185 //                {
186 //                    if(!q[1].empty())
187 //                        q[1].pop();
188 //                    if(!q[2].empty())
189 //                        q[2].pop();
190 //                    if(!q[3].empty())
191 //                        q[3].pop();
192 //                }
193 ////              cout<<i<<' '<<j<<endl;
194 ////              while(!q[1].empty())
195 ////                  q[1].pop();
196 ////              while(!q[2].empty())
197 ////                  q[2].pop();
198 ////              while(!q[3].empty())
199 ////                  q[3].pop();
200 //                
201 //                memset(s,0,sizeof(s));
202 //                bfs(data[i].x,data[i].y);
203 ////              cout<<s[a1][b1]<<' '<<s[a2][b2]<<endl;
204 //                if(s[a1][b1]!=0&&s[a2][b2]!=0&&s[a1][b1]+s[a2][b2]<minn)
205 //                    minn=s[a1][b1]+s[a2][b2];
206 //            }
207 // //           cout<<sum1<<' '<<sum2<<endl; 
208 //    cout<<minn<<endl;
209  //   cout << "
" << (double)clock() / CLOCKS_PER_SEC;
210  //     cout<<sum<<endl; 
211     return 0;
212 }

算法专题训练 搜索a-T3 Ni骑士(ni)

算法专题训练搜索a-T3 Ni骑士(ni)