HDU Nightmare （BFS）

在有一炸彈(定時6分鐘)地圖中0是牆，1是空地，2是起點，3是終點，4是炸彈重置點(重新定時為６)，

問能否到達安全到達終點，并求出需要的最小時間. 

//AC  HDU 1072

#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<cstring>
#include<cmath>
using namespace std;
int mp[10][10];
int usedtimearr[10][10];
int lefttimearr[10][10];

int nextx[4] = {0 , 0 , -1 , 1};
int nexty[4] = {-1 , 1 , 0, 0 };
int m,n;
int startx, starty , endx , endy;
int restime;
struct Point
{
    int x;
    int y;
    int usedtime;
    int lefttime;
};

int BFS( )
{
    queue<Point> q;
    Point startp;
    startp.x = startx; startp.y = starty;
    startp.lefttime = 6; startp.usedtime = 0;

    q.push(startp);

    while( !q.empty())
    {
        //cout<<"@";
        Point temp = q.front();
        q.pop();

        if (temp.x == endx && temp.y ==endy)
        {
            if( temp.usedtime < restime)
            {
                restime = temp.usedtime;
            }
            return 1;
        }

        Point nextp;


        for( int i = 0; i < 4; i++)
        {
          //  cout<<'*';
            nextp.x = temp.x + nextx[i];
            nextp.y = temp.y + nexty[i];

           // cout<<nextp.x<<" "<<nextp.y<<" "<<nextp.usedtime<<" "<<nextp.lefttime<<endl;
            if ( mp[nextp.x][nextp.y] == 0 )
            {
                continue;
            }
            if ( nextp.x <=0 || nextp.x > n || nextp.y <=0 || nextp.y >m)
            {
                continue;
            }
            nextp.usedtime = temp.usedtime +1;
            nextp.lefttime  = temp.lefttime -1;

            if (nextp.lefttime == 0 )
            {
                continue;
            }
            if( usedtimearr[nextp.x][nextp.y] < nextp.usedtime && lefttimearr[nextp.x][nextp.y] > nextp.lefttime)
            {
                continue;
            }
            if ( mp[nextp.x][nextp.y] == 4)
            {
                nextp.lefttime = 6;
            }
            if ( usedtimearr[nextp.x][nextp.y] > nextp.usedtime && lefttimearr[nextp.x][nextp.y] < nextp.lefttime)
            {
                usedtimearr[nextp.x][nextp.y] = nextp.usedtime;
                lefttimearr[nextp.x][nextp.y] = nextp.lefttime;
            }

           // cout<<nextp.x<<" "<<nextp.y<<" "<<nextp.usedtime<<" "<<nextp.lefttime<<endl;
            q.push(nextp);

        }

    }

    return 0;
}

int main()
{
   // freopen("ab.txt" , "r" , stdin );
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>mp[i][j];
                usedtimearr[i][j] = INT_MAX;
                lefttimearr[i][j] = 0;
                if (mp[i][j] == 2)
                {
                    startx = i; starty = j;
                }
                if (mp[i][j] == 3)
                {
                    endx = i; endy = j;
                }
            }
        }


        // 0-not walk  1-can walk 2-start 3-exit 4-+6s
        //求最短的時間
        usedtimearr[startx][starty] = 0;
        lefttimearr[startx][starty] = 6;
        int res = BFS( );
        if (res == 0 )
        {
            cout<<-1<<endl;
            continue;
        }
        cout<<usedtimearr[endx][endy]<<endl;

    }
}
           

今天 ，，，果粒叔在微網誌回複我了哈哈哈哈哈。。。。。。

給愛豆打call.

明兒再寫，，仿佛自己的方法有些愚笨。