逃出克隆岛 (codevs 2059)

较普通的走迷宫的题

传送门 ：codevs 2059 逃出克隆岛

思路 ：BFS 即可    PS ：传送门 不必重复使用

#include <iostream>

#include <cstdio>

#define Max 2020

using namespace std;

int N, M;

int start_x, start_y, end_x, end_y;

int move_x [] = {, -, , }, move_y [] = {, , , -};

char map [Max][Max];

int queue [Max][];

int cost [Max * ];

bool door [Max][Max], visit [Max][Max];

bool flag;

int pay;

void BFS (int start_x, int start_y)

{

    int head_cur = , tail_cur = ;

    visit [start_x][start_y] = true;  //标记当前点为 已访问

    queue [][] = start_x; //将起点入队列

    queue [][] = start_y;

    cost [] = ;  // 当前的花费为0

    while (head_cur < tail_cur)

    {

        head_cur++;

        for (int i = ; i <= ; i++)

        {

            int x = queue [head_cur][] + move_x [i];

            int y = queue [head_cur][] + move_y [i];

            if (x == end_x && y == end_y)  // 如果到达了终点， flag 标记为 true 直接输出花费即可

            {

                flag = true;

                cout << cost [head_cur];

                return;

            }

            if (x >  && x <= N && y >  && y <= M && map [x][y] != '#' && visit [x][y] == false) // 在边界内，且当前点 不是障碍点 且当前点未访问

            {

                if (door [x][y] == true)  //如果此点为传送门，且当前传送门可以走

                {

                    door [x][y] = false;  // 标记为已走

                    for (int i = ; i <= N; i++)

                        for (int j = ; j <= M; j++)  //在全图内搜索 可走的传送门

                            if (door [i][j] == true)

                            {

                                tail_cur++;

                                queue [tail_cur][] = i; //将当前传送到的位置加入队列

                                queue [tail_cur][] = j;

                                door [i][j] = false;  // 标记此传送门为已走

                                cost [tail_cur] = cost [head_cur];  //由于传送门没有花费， 所以等于前一个点的花费

                            }

                }

                tail_cur++;  // 如果不是传送门 ，将当前位置加入队列

                queue [tail_cur][] = x;

                queue [tail_cur][] = y;

                visit [x][y] = true;  // 标记为已访问

                if (map [x][y] == '*') //如果走此点需要花费

                    cost [tail_cur] = cost [head_cur] + pay;  // 上一个点的花费 再加一次花费 即为当前位置的花费

                else

                    cost [tail_cur] = cost [head_cur];  // 若是普通点，则当前点的花费等于上一个点的花费

            }

        }

    }

}

int main()

{

    ios :: sync_with_stdio (false);

    cin >> N >> M >> pay;

    for (int i = ; i <= N; i++)

        for (int j = ; j <= M; j++)

        {

            cin >> map [i][j];

            if (map [i][j] == 'Y')  // 记录起点

            {

                start_x = i;

                start_y = j;

            }

            else if (map [i][j] == 'C')  //记录终点

            {

                end_x = i;

                end_y = j;

            }

            else if (map [i][j] == 'P')  //记录传送门的位置 标记当前传送门可访问

                door [i][j] = true;

        }

    BFS (start_x, start_y);

    if (flag == false)    // 若走不通

        cout << "screw you!";

    return ;

}