POJ 2049 Finding Nemo 優先隊列 STL

POJ 2049 Finding Nemo 優先隊列 STL

題目利用了《海底總動員》的情節，小丑魚尼莫迷路了，他老爸去營救他便是題意。

題目給出了這樣的地圖，說是假設地圖由牆和門組成，忽略牆的厚度，地圖上有門，沒有牆的地方是可以自由行動的問可以經過最少多少道門便可以營救到尼莫。

這個題給的數據是牆的交點為整數點，但魚爸爸實在非牆的地方自由移動。

因此，這個題有兩個難點：

1.如果建圖保存地圖

2.如何在地圖上遍歷

由於題目是給出一個點（x，y），來表示一段牆

我便用一對X，Y來表示地圖的塊空間

用一個二維結構體數組保存，而每個結構體就是這樣的一個單元。

如何保存便解決了。

至於遍歷，果斷BFS，但是因為要保證走的門最少那麼就有一個在遍歷下一個方格的時候存在選擇哪條路的問題

為了保證走過的門最少，因此選用優先隊列，不是讓先入隊列的先出隊，而是讓走的門最少的先出隊。

要用優先隊列，第一次嘗試用STL，在

priority_queue,less > que;

第三個參數出現了問題，不知道怎麼寫。

百度到說需要自己重新寫重載，但不明白怎麼寫，好像函數內，函數外重載都不好弄，STL應該也不會讓我這樣（因為理解錯為給類priority_queue寫運算符重載了）

看了他們的代碼發現自己想錯了， 應該是把自己定義的結構體看為類，為這個類寫運算符重載

然後寫到結構體裡便好了。

struct Tmp
{
    int x,y;
    int t;

    bool operator<(const Tmp & b) const
    {
        return t > b.t;
    }
};

後期調試的過程中總是問題不斷，最大的問題便是我忽略了X,Y應該互換位置表示，畢竟題目給的坐標和二維數組的表示坐標是不一樣的。

最後一組測試數據：

1 6
1 2 1 5
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0.5 5.5
答案是2
而不是4

在討論裡看到的數據，就是這個讓我發現了X,Y需要互換的大漏洞，然後就A了。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#define MAX 1000000

using namespace std;

struct node
{
    int eg[4];
} MAP[300][300];

bool vis[300][300];

struct Tmp
{
    int x,y;
    int t;

    bool operator<(const Tmp & b) const
    {
        return t > b.t;
    }
};

int bfs (int x,int y,int fx,int fy)
{
    Tmp tmp,now;
    priority_queue,less > que;
    memset(vis,0,sizeof(vis));

    now.x = x;
    now.y = y;
    now.t = 0;

    que.push (now);

    while (!que.empty())
    {
        now = que.top();
        que.pop();

        //cout << now.t << endl;

        if (now.x == fx && now.y == fy)
            return now.t;

        if (!vis[now.x][now.y])
        {
            //cout << now.x << ' ' << now.y  << '-' << now.t<< endl;
            vis[now.x][now.y] = 1;
            for (int i = 0;i < 4;i++)
            {
                if (MAP[now.x][now.y].eg[i] != 1)
                {
                    tmp = now;

                    if (i == 0)
                    {
                        tmp.x--;
                        if (MAP[now.x][now.y].eg[i] == 2)
                            tmp.t++;
                    }else if (i == 1)
                    {
                        tmp.y++;
                        if (MAP[now.x][now.y].eg[i] == 2)
                            tmp.t++;
                    }else if (i == 2)
                    {
                        tmp.x++;
                        if (MAP[now.x][now.y].eg[i] == 2)
                            tmp.t++;
                    }else if (i == 3)
                    {
                        tmp.y--;
                        if (MAP[now.x][now.y].eg[i] == 2)
                            tmp.t++;
                    }
                    if (tmp.x>=0 && tmp.y >= 0 && tmp.x < 300 && tmp.y < 300 && !vis[tmp.x][tmp.y])
                        que.push(tmp);
                }
            }
        }
    }

    return -1;
}

int main (void)
{
    int m,k;

    while (scanf (%d%d,&m,&k),m != -1 || k != -1)
    {
        memset(MAP,0,sizeof (MAP));

        int x,y,d,t,i;

        for (i = 0;i < m;i++)
        {
            scanf (%d%d%d%d,&x,&y,&d,&t);

            int j;
            if (d) //y
            {
                for (j = 0;j < t;j++)
                {
                    MAP[299 - y - j][x].eg[3] = 1;
                    MAP[299 - y - j][x - 1].eg[1] = 1;
                }
            }else  //x
            {
                for (j = 0;j < t;j++)
                {
                    MAP[299 - y][x + j].eg[2] = 1;
                    MAP[299 - y + 1][x + j].eg[0] = 1;
                }
            }
        }

        for (i = 0;i < k;i++)
        {
            scanf (%d%d%d,&x,&y,&d);

            int j;
            if (d) //y
            {

                MAP[299 - y][x].eg[3] = 2;
                MAP[299 - y][x - 1].eg[1] = 2;
            }else  //x
            {
                MAP[299 - y][x].eg[2] = 2;
                MAP[299 - y + 1][x].eg[0] = 2;
            }
        }

        double fx,fy;

        scanf (%lf%lf,&fx,&fy);
        int ifx = int (fx);
        int ify = int (fy);

        if (k == 0 && m == 0)
            printf (0
);
        else if (fx < 0 || fx > 199 || fy < 0 || fy > 199)
            printf(0
);
        else
        {
            int ans = bfs (299,0,299 - ify,ifx);
            printf (%d
,ans);
        }
    }

    return 0;
}