妇添小有一个很厉害的技能：发现吃的！如果有好吃的东西，不论多远，只要一闻就能知道在哪里。这天他刚刚在程设rejudge完，忽然鼻子一抽——有吃的！他决定马上赶去吃这么好吃的东西。
语文男为了考验妇添小的品味，在路中间放了很多馒头，看他会不会饿的先吃馒头。妇添小当然不会让这种雕虫小计得逞！为了保持自己的品味，他决定绕开所有的馒头。Eureka受到妇添小邀请，运用绝世法力构造了很多传送点，任意两个传送点之间都能瞬移（当然传不传，传到哪里都可以随心所欲）。妇添小每次移动只能走上下左右四个方向（瞬移除外，并且瞬移不耗费时间）。现在，妇添小最短多长时间能吃到好吃的东西呢？
（当然，为了出题我们隐瞒了一些事实：不仅好吃的不见了，路上的馒头竟然也不翼而飞了，这真真是个悲伤的故事T.T）
输入：
第一行包含两个数字n,m（1<=n,m<=2000）
接下来包含n行，每行m个字符，表示现在的地图。'.'表示空地，'M‘表示馒头，‘E’表示传送点，'N'表示妇添小所在的位置，'C'表示吃的。'N'和‘C'在地图中出现且仅出现一次。
输出：
一个数字，表示妇添小最快能多长时间吃到好吃的。如果永远吃不到，只能说明传送点不够多，输出“Bad Eureka”。
提示：如果时间显示是0.004等很短的时间，但是最后评测为TLE，这时候实际上是因为开的数组过大，超出了内存限制。
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 以文本方式显示 6 6↵ ...E..↵ EMM.M.↵ .M..M.↵ .MC.M.↵ .MMM..↵ N..E..↵ 以文本方式显示 7↵ 1秒 64M 0 题解： 看着就是一个简单的搜索题目（实际也不太难），我一开始想的办法是求所有E到C的距离找出最小值记为a，找N到最近的E的距离记为b，N不走E直接到C的距离为c，最后看a+b和c哪个大。但是一开始用DFS交了几发，出了3个RE，不知道是什么鬼。然后后来用BFS，有一个超时。后来发现是找所有E到C的距离导致时间复杂度太高，直接找C到最近的E的距离记为a即可。然后就过了。 可是我还是不知道为什么不能用DFS。 代码： #include<stdio.h> #include<string.h> char map1[2005][2005]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1, -1 }; int n, m; int vis[2005][2005] = { 0 }; struct node { short x, y; int index; }q[4000005]; int bfs(int x1, int y1) { memset(vis, 0, sizeof(vis)); // memset(q, 0, sizeof(q)); int front = 0, rear = 1, a, b; q[front].x = x1; q[front].y = y1; q[front].index = 0; vis[x1][y1] = 1; while (front<rear){ if (map1[q[front].x][q[front].y] == 'C') return q[front].index; for (int i = 0; i<4; i++){ a = q[front].x + dx[i]; b = q[front].y + dy[i]; if (a<0 || b<0 || a>n - 1 || b>m - 1 || vis[a][b] || map1[a][b] == 'M') continue; else{ vis[a][b] = 1; q[rear].x = a; q[rear].y = b; q[rear].index = q[front].index + 1; rear++; } } front++; } return 0x3f3f3f3f; } int bfs2(int x1, int y1) { memset(vis, 0, sizeof(vis)); // memset(q, 0, sizeof(q)); int front = 0, rear = 1, a, b; q[front].x = x1; q[front].y = y1; q[front].index = 0; vis[x1][y1] = 1; while (front<rear){ if (map1[q[front].x][q[front].y] == 'E') return q[front].index; for (int i = 0; i<4; i++){ a = q[front].x + dx[i]; b = q[front].y + dy[i]; if (a<0 || b<0 || a>n-1 || b>m-1 || vis[a][b]||map1[a][b]=='M') continue; else{ vis[a][b] = 1; q[rear].x = a; q[rear].y = b; q[rear].index = q[front].index + 1; rear++; } } front++; } return 0x3f3f3f3f; } int main() { scanf("%d%d", &n, &m); getchar(); int i, j; int sx, sy,ex,ey; for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { scanf("%c", &map1[i][j]); if (map1[i][j] == 'N') { sx = i; sy = j; } if (map1[i][j] == 'C') { ex = i; ey = j; } } getchar(); } int min1, min2, min3; min1 = bfs2(ex, ey); min2 = bfs2(sx, sy); min3 = bfs(sx, sy); int ans; if ((min1 == 0x3f3f3f3f || min2 == 0x3f3f3f3f) && min3 == 0x3f3f3f3f) printf("Bad Eureka\n"); else { ans = (min1 + min2) < min3 ? (min1 + min2) : min3; printf("%d\n", ans); } }