问题描述
妇添小有一个很厉害的技能：发现吃的！如果有好吃的东西，不论多远，只要一闻就能知道在哪里。这天他刚刚在程设rejudge完，忽然鼻子一抽——有吃的！他决定马上赶去吃这么好吃的东西。
语文男为了考验妇添小的品味，在路中间放了很多馒头，看他会不会饿的先吃馒头。妇添小当然不会让这种雕虫小计得逞！为了保持自己的品味，他决定绕开所有的馒头。Eureka受到妇添小邀请，运用绝世法力构造了很多传送点，任意两个传送点之间都能瞬移（当然传不传，传到哪里都可以随心所欲）。妇添小每次移动只能走上下左右四个方向（瞬移除外，并且瞬移不耗费时间）。现在，妇添小最短多长时间能吃到好吃的东西呢？
（当然，为了出题我们隐瞒了一些事实：不仅好吃的不见了，路上的馒头竟然也不翼而飞了，这真真是个悲伤的故事T.T）
输入：
第一行包含两个数字n,m（1<=n,m<=2000）
接下来包含n行，每行m个字符，表示现在的地图。'.'表示空地，'M‘表示馒头，‘E’表示传送点，'N'表示妇添小所在的位置，'C'表示吃的。'N'和‘C'在地图中出现且仅出现一次。
输出：
一个数字，表示妇添小最快能多长时间吃到好吃的。如果永远吃不到，只能说明传送点不够多，输出“Bad Eureka”。
提示：如果时间显示是0.004等很短的时间，但是最后评测为TLE，这时候实际上是因为开的数组过大，超出了内存限制。
| | 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
大致思路：
一种思路就是利用广度优先搜索，进行三次搜索，N到E的距离S1，C到E的距离S2，N到C的距离S3，进行搜索，如果可以到的话就比较S3和S1+S2的大小，去较小的一个。
另一种思路就是运用动态规划，从结束的那个点开始向前搜索，每一次都只走该位置上下左右中步数较少的那一个。
具体实现：
第一种思路就是自己用数组模拟一个队列，然后对数组进行操作，可以走就加入队列，并把他的父亲节点去掉，不可以走就不加入队列。
第二种思路就是设置一个状态数组记录每个位置所要走的步数，递归即可。
注意：
（1）由于数据量比较大，所以开数组的时候要尽量的使用恰当的数据类型，比如记录每个点的信息，就用char型的；记录每个点是否走过可以用char型的或是short型的（short型和int型的是不一样的）：记录每个点的坐标也可以用short型的，这样就可以节省好多空间。队列也可以循环利用。
（2）记录信息的时候看自己是从0位开始的还是从1位开始的，在搜索的时候注意一下边界，防止越界。
实现代码
<span style="font-family:Microsoft YaHei;font-size:14px;">#include<stdio.h>
#include<string.h>int m,n;
char map[2004][2004];
struct queues
{short heng;short zong;int ceng;
}que[4000005];
int dheng[4]={1,0,-1,0};
int dzong[4]={0,1,0,-1};
int BFS1(int x,int y)
{int start=0;int last=1;int k,tempi,tempj; short visit[2004][2004]; int t1,t2;t1=x;t2=y; //找E memset(visit,0,sizeof(visit));visit[t1][t2]=1;que[0].heng=t1;que[0].zong=t2;que[0].ceng=0;while(start<last){if(map[que[start].heng][que[start].zong]=='E')return que[start].ceng;for(k=0;k<4;k++){tempi=que[start].heng+dheng[k];tempj=que[start].zong+dzong[k];if(tempi<0||tempi>m-1||tempj<0||tempj>n-1){continue;}if(map[tempi][tempj]!='M'&&!visit[tempi][tempj]){visit[tempi][tempj]=1;que[last].heng=tempi;que[last].zong=tempj;que[last].ceng=que[start].ceng+1;last++;}}start++;}return -1;
}
int BFS2(int x,int y)
{int start=0;int last=1;int k,tempi,tempj;short visit[2004][2004]; int t1,t2;t1=x;t2=y; memset(visit,0,sizeof(visit));visit[t1][t2]=1;que[0].heng=t1;que[0].zong=t2;que[0].ceng=0;while(start<last){if(map[que[start].heng][que[start].zong]=='C')return que[start].ceng;for(k=0;k<4;k++){tempi=que[start].heng+dheng[k];tempj=que[start].zong+dzong[k];if(tempi<0||tempi>m-1||tempj<0||tempj>n-1){continue;}if(map[tempi][tempj]!='M'&&!visit[tempi][tempj]){visit[tempi][tempj]=1;que[last].heng=tempi;que[last].zong=tempj;que[last++].ceng=que[start].ceng+1;}}start++;}return -1;
}
int main()
{short i,j;short x1,y1,x2,y2;int count1,count2,count3,count;scanf("%d%d",&m,&n);getchar(); for(i=0;i<m;i++){for(j=0;j<n;j++){scanf("%c",&map[i][j]);if(map[i][j]=='N'){x1=i;y1=j;}if(map[i][j]=='C'){x2=i;y2=j;}}getchar();}int flag=0;count1=BFS1(x1,y1);count2=BFS1(x2,y2);count3=BFS2(x1,y1);if(count1!=-1&&count2!=-1){if(count3==-1){count=count1+count2; }else{if(count3<count1+count2){count=count3;}else{count=count1+count2;}} }else{if(count3==-1){flag=1;}else{count=count3;}}if(flag==1){printf("Bad Eureka\n");}else{printf("%d\n",count);}return 0;}</span>
