题目描述
这次题目的主角Chell必须解决GLaDOS提出的一个新的难题。Chell现在在一个布局可以表示为N行M列的房间当中，每一个细分的方格中，可以是一下几种情况之一： ·障碍物-墙（表示为‘#’） ·Chell最初始的位置（表示为‘C’） ·Chell必须到达的终点（表示为‘F’） ·空位置（表示为‘.’） Chell手上有一门所谓的“门枪”，这把枪可以在墙上创造一个入口，每次移动时，她可以进行以下操作中的一种操作： ·向上、下、左、右移动到相邻区域（无法移动到有墙的区域） ·如果上、下、左、右方向有一堵墙（不是相邻的上下左右方向），则可以使用“门枪”在墙上创造一个入口，这个入口只能从被激活的这一侧进入，同一时刻最多只可激活两个入口。如果在已经存在两个入口时再激活一个入口，那么，先创建的那个入口就会消失。创造这种入口所消耗的时间可忽略不计，即记为消耗0时间。 ·如果Chell在一个与墙壁相邻的位置，且这个墙面向她的这一侧有一个入口，且现在有两个入口，那么Chell就可以通过这个入口到另一个入口前的一个无障碍位置。此移动持续一个单位时间。 Chell想知道，她最少需要花费多少时间，从起点到终点。 注意：房间两侧总有墙壁，字母‘C’和‘F’只会出现一次。
输入格式
第一行输入两个正整数N、M（4≤N，M≤500），表示房间的行列数。 接下来输入一个N行M列的地图，每个格子包含‘C’，‘.’，‘F’，‘#’这四种中的一种字符。
输出格式
输出Chell从起点到终点最少需要花费的时间，如果她不能到达终点，则输出“nemoguce”。
样例
样例输入1

4 4

样例输出1

2
样例输入2

6 8
#
#.…F#
#C.…#
#…#…#
#…
#
样例输出2

讯享网

4
样例输入3

4 5

样例输出3

nemoguce
数据范围与提示
对于样例2，首先在起点的左侧（3,1）和下侧（6,2）建立一个入口，那么，消耗1个单位时间，Chell就可以到达（5,2）。到达（5,2）后，再在右边（5,7）的墙上建立一个入口，此时，存在的两个入口分别在(6,2)和(5,7)这两个位置，再通过1个单位时间到达（5,6）这个位置。同理，在往上（1,6）建立一个入口，再通过入口，从（5,6）到达（2,6）,再向右一步到达终点。这当中一共消耗了4个单位时间。

解题思路

#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<iostream> #include<cmath> #include<algorithm> using namespace std; struct node{ 
    int u,v; node(){ 
   }; node(int U,int V){ 
    u = U,v = V; } }; int n,m,s,e,dis[]; char mase[505][505]; bool vis[]; vector <node>G[]; void spfa(){ 
    memset(dis,0x3f,sizeof(dis)); dis[s] = 0; queue<int>Q; Q.push(s); vis[s] = 1; while (!Q.empty()){ 
    int p = Q.front(); Q.pop(); vis[p] = 0; int xx = G[p].size(); for (int i = 0;i < xx;i ++){ 
    int u = G[p][i].u,v = G[p][i].v; if (dis[u] > dis[p] + v){ 
    dis[u] = dis[p] + v; if (!vis[u]){ 
    Q.push(u); vis[u] = 1; } } } } if (dis[e] == 0x3f3f3f3f) printf("nemoguce\n"); else printf("%d",dis[e]); } int main(){ 
    scanf ("%d%d",&n,&m); for (int i = 1;i <= n;i ++){ 
    scanf("\n"); for (int j = 1;j <= m;j ++){ 
    scanf ("%c",&mase[i][j]); if (mase[i][j] == 'C'){ 
    mase[i][j] = '.'; s = i * m + j; } if (mase[i][j] == 'F'){ 
    mase[i][j] = '.'; e = i * m + j; } } } for (int i = 1;i <= n;i ++){ 
    for (int j = 1;j <= m;j ++){ 
    if (mase[i][j] == '#') continue; if (j + 1 <= m && mase[i][j + 1] != '#'){ 
    G[i * m + j].push_back(node(i * m + j + 1,1)); G[i * m + j + 1].push_back(node(i * m + j,1)); } if (i + 1 <= n && mase[i + 1][j] != '#'){ 
    G[(i + 1) * m + j].push_back(node(i * m + j,1)); G[i * m + j].push_back(node((i + 1) * m + j,1)); } int tot1 = 0,k1 = i - 1; while (mase[k1][j] != '#'){ 
    k1 --; tot1 ++; } int tot2 = 0,k2 = i + 1; while (mase[k2][j] != '#'){ 
    k2 ++; tot2 ++; } int tot3 = 0,k3 = j - 1; while (mase[i][k3] != '#'){ 
    k3 --; tot3 ++; } int tot4 = 0,k4 = j + 1; while (mase[i][k4] != '#'){ 
    k4 ++; tot4 ++; } int min_tot = min(tot1,min(tot2,min(tot4,tot3))) + 1; G[i * m + j].push_back(node ((k1 + 1) * m + j,min_tot)); G[i * m + j].push_back(node ((k2 - 1) * m + j,min_tot)); G[i * m + j].push_back(node (i * m + k3 + 1,min_tot)); G[i * m + j].push_back(node(i * m + k4 - 1,min_tot)); } } spfa(); }