AOJ.866 飞越原野 (三维BFS)

题意分析

点我挑战题目

相比于普通的BFS，要多一维来记录当前剩余的体力。而且还要额外的一层循环来处理，飞过的路程。

代码总览

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <sstream>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <cmath>

#define INF 0x3f3f3f3f

#define nmax 200

#define MEM(x) memset(x,0,sizeof(x))

using namespace std;

bool visit[nmax][nmax][nmax],isfind =  false;

char mp[nmax][nmax];

struct nod{

    int x,y,e;

}node[nmax];

int m,n,o,ans;

int spx[] = {0,1,0,-1};

int spy[] = {1,0,-1,0};

bool check(int x, int y, int e)

{

    if(x<0 || x >= m || y<0 || y>=n || mp[x][y] =='L' || visit[x][y][e] == true)

        return false;

    else

        return true;

}

void bfs()

{

    nod temp;

    temp.x = 0; temp.y = 0; temp.e = o;

    visit[temp.x][temp.y][temp.e] = true;

    queue<nod> q;

    if(!q.empty()) q.pop();

    q.push(temp);

    ans = 0;

    while(!q.empty()){

        int nowsize = q.size();

        while(nowsize--){

            nod tep = temp = q.front();

            q.pop();

            // get final or not

            if(tep.x == m-1 && tep.y == n-1){

                isfind = true;

                break;

            }

            for(int i = 0 ;i<4;++i){

                tep.x =temp.x + spx[i];

                tep.y =temp.y + spy[i];

                if(check(tep.x,tep.y,tep.e)){

                    visit[tep.x][tep.y][tep.e] = true;

                    q.push(tep);

                }

            }

            for(int i = 0; i<4;++i){

                for(int j = 1; j<=temp.e;++j){

                    tep.x = temp.x + spx[i] *j;

                    tep.y = temp.y + spy[i] *j;

                    tep.e = temp.e - j;

                    if(check(tep.x,tep.y,tep.e)){

                        visit[tep.x][tep.y][tep.e] = true;

                        q.push(tep);

                    }

                }

            }

        }

        if(isfind) break;

        ans++;

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d %d %d",&m,&n,&o) != EOF){

        MEM(visit);

        isfind  = false;

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

            scanf("%s",mp[i]);

        bfs();

        if(isfind) printf("%d\n",ans);

        else printf("impossible\n");

    }

    return 0;

}