HDU1072

题目链接

传送门

题目大意

给你一个图,0代表墙,1代表可以走,2代表起始点,3代表结束点,4代表时间重置点。

解题思路

逃生搜索的一种变形,主要在它的生存时间可以重置。对起始点进行BFS搜索,vis数组记录该点是否走过。在四个方向搜索时,如果满足坐标不越界,该点没走过并且该点不是墙,则进行if判断:
(1)此时坐标恰好等于终点,返回step;
(2)maps等于1,时间减1;
(3)maps等于4,时间重置,标记走过。如果最后队列为空时也不能走出,返回-1.

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <cassert>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
#define REP0(i, n) for (int i=0;i<int(n);++i)  
#define REP1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
using namespace std;  
#define REP(i, n) for (int i=0;i<int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
#define REP_1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)  
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)  
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)  
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)  
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)  
#define REP_N(i, n) for (i=0;i<int(n);++i)  
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)  
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)  
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)  
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)  
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)  
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)  
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)  
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)  
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)  
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)  

//#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)  
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)  
#define REP_S(it, str) for (char*it=str;*it;++it) // 用于字符串的 .. .  
#define REP_G(it, u) for (int it=hd[u];it;it=suc[it]) // 用于图论的 .. .  
#define DO(n) for ( int ____n ## __line__ = n; ____n ## __line__ -- ; )  
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)  
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)  
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)  
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)  
#define ALL(A) A.begin(), A.end()  
#define LLA(A) A.rbegin(), A.rend()  
#define CPY(A, B) memcpy(A, B, sizeof(A))  
#define INS(A, P, B) A.insert(A.begin() + P, B)  
#define ERS(A, P) A.erase(A.begin() + P)  
#define BSC(A, X) find(ALL(A), X) // != A.end()  
#define CTN(T, x) (T.find(x) != T.end())  
#define SZ(A) int(A.size())  
#define PB push_back  
#define MP(A, B) make_pair(A, B)  
#define PTT pair<T, T>  
#define fi first  
#define se second  
#define ALL(A) A.begin(), A.end()  
#define LLA(A) A.rbegin(), A.rend()  
#define CPY(A, B) memcpy(A, B, sizeof(A))  
#define INS(A, P, B) A.insert(A.begin() + P, B)  
#define ERS(A, P) A.erase(A.begin() + P)  
#define BSC(A, X) find(ALL(A), X) // != A.end()  
#define CTN(T, x) (T.find(x) != T.end())  
#define SZ(A) int(A.size())  
#define PB push_back  
#define MP(A, B) make_pair(A, B)  
#define PTT pair<T, T>  
#define fi first  
#define se second  

#define Rush int T____; RD(T____); DO(T____)  
#define Rush int T____; RD(T____); DO(T____)  

#define Display(A, n, m) {                      \  
    REP(i, n){                                  \  
        REP(j, m) cout << A[i][j] << " ";       \  
        cout << endl;                         \  
    }                                           \  
}  

#define Display_1(A, n, m) {                    \  
    REP_1(i, n){                                \  
        REP_1(j, m) cout << A[i][j] << " ";     \  
        cout << endl;                         \  
    }                                           \  
}  
typedef long long LL;  
//typedef long double DB;  
typedef double DB;  
typedef unsigned UINT;  
typedef unsigned long long ULL;  

typedef vector<int> VI;  
typedef vector<char> VC;  
typedef vector<string> VS;  
typedef vector<LL> VL;  
typedef vector<DB> VD;  
typedef map<int, int> MII;  
typedef map<string, int> MSI;  
typedef map<LL, int> MLI;  
typedef map<DB, int> MDI;  
typedef pair<int, int> PII;  
typedef pair<int, bool> PIB;  
typedef pair<LL, LL> PLL;  
typedef vector<PII> VII;  
typedef vector<VI> VVI;  
typedef vector<VII> VVII;  
const int dx[] = {-1, 0, 1, 0};  
const int dy[] = {0, 1, 0, -1};  
const int MOD = 1000000007;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 1LL << 60;  
const DB EPS = 1e-9;  
const DB OO = 1e15;  
const DB PI = acos(-1.0); //M_PI;  
#define N 81  
int n , m , i , j , k , t , flag;  
int maps[N][N] , vis[N][N] , d[4][2] = {-1, 0, 1, 0, 0, -1, 0 ,1};  

struct node  
{  
    int x , y , time ,step;  
};  


int bfs(node st , node ed)  
{  
    memset(vis , 0 , sizeof(vis));  
    queue<node> q;  
    node now , next;  
    now.x = st.x;  
    now.y = st.y;  
    now.time = 6;  
    now.step = 0;  
    vis[st.x][st.y] = 1;  
    q.push(now);  
    while(!q.empty())  
    {  
        now = q.front();  
        q.pop();  
        REP(i , 4)  
        {  
            next.x = now.x + d[i][0];  
            next.y = now.y + d[i][1];  
            next.step = now.step + 1;  
            next.time = now.time - 1;  
            if(next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && !vis[next.x][next.y] && next.time >= 1 && maps[next.x][next.y] != 0)  
            {  
                if(next.x == ed.x && next.y == ed.y)  
                    return next.step;  
                else if(maps[next.x][next.y] == 4)  
                {  
                    next.time = 6;  
                    vis[next.x][next.y] = 1;  
                }  
                else if(maps[next.x][next.y] == 1)  
                    next.time = now.time - 1;  
                q.push(next);  
            }  
        }  
    }  
    return -1;  
}  


int main()  
{  
    #ifdef ZH  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    node st ,ed;  
    while(T--)  
    {  
        scanf("%d%d",&n,&m);  
        memset(maps , 0 , sizeof(maps));  
        REP(i , n)  
        {  
            REP(j , m)  
            {  
                scanf("%d",&maps[i][j]);  
                if(maps[i][j] == 2)  
                {  
                    st.x = i;  
                    st.y = j;  
                }  
                else if(maps[i][j] == 3)  
                {  
                    ed.x = i;  
                    ed.y = j;  
                }  
            }  
        }  
        printf("%d\n",bfs(st , ed));  
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图