程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj3652 Maze(bfs)

zoj3652 Maze(bfs)

編輯:C++入門知識

zoj3652 Maze(bfs)


Maze

Time Limit: 2 Seconds Memory Limit: 65536 KB

Celica is a brave person and believer of a God in the bright side. He always fights against the monsters that endanger humans. One day, he is asked to go through a maze to do a important task.

The maze is a rectangle of n*m, and Celica is at (x1, y1) at the beginning while he needs to go to (x2, y2). And Celica has a Mobility of l. When he moves a step the movility will decreased by 1. If his mobility equals to 0, he can't move anymore in this turn. And no matter how much mobility Celica uses in one turn, his movility will become l again in the next turn. And a step means move from one lattice to another lattice that has an adjacent edge.

However, due to the world's rule and the power of magic, there is something called Dominance in the maze. Some lattices may be dominated by some monsters and if Celica goes into these lattices, his mobility will be reduced to 0 at once by the monster's magic power. And monsters have strong Domain awareness so one lattice won't be dominated by more than one monster.

But luckily, Celica gets a strong power from his God so that he can kill this monsters easily. If Celica goes into a lattice which a monster stands on, he can kill the monster without anytime. If a monsters is killed, the lattices it dominates will no longer be dominated by anyone(or we can say they are dominated by Celica) and these lattices will obey the rule of mobility that normal lattices obey.

As for the task is so important that Celica wants to uses the least turn to go to (x2, y2). Please find out the answer.


PS1: It doesn't matter if Celica doesn't kill all the monsters in the maze because he can do it after the task and a monster may appear at a lattice that is not dominated by it, even a lattice that is not dominated by any monsters.

PS2: We define (1,1) as the top left corner. And monsters won't move.

PS3: No matter which lattice Celia gets in, the change of mobility happens first.

PS4: We promise that there is no two monsters have same position and no monster will appear at the start point of Celica.

Input


The first contains three integers, n, m, l.(1≤n, m≤50, 1≤l≤10)

Then there follows n lines and each line contains m integers. The j-th integer p in the line i describe the lattice in the i line and j row. If p euqals to -1, it means you can't get into it. If p euqals to 0, it means the lattice is not dominated by any monster. If p is larger than 0, it means it is dominated by the p-th monster.

And then in the n+2 line, there is an integer k(0≤k≤5) which means the number of monster.

Then there follows k lines. The i-th line has two integers mean the position of the i-th monster.

At last, in the n+k+3 lines, there is four integers x1, y1, x2, y2.

Output

If Celica can't get to the (x2, y2), output We need God's help!, or output the least turn Celica needs.

Sample Input

5 5 4
2 2 2 1 0
-1 2 2 -1 1
2 2 2 1 1
1 1 1 1 0
1 2 2 -1 0
2
4 2
1 1
5 1 1 5
5 5 4
1 1 1 1 1
1 2 2 -1 -1
2 2 -1 2 2
-1 -1 2 2 2
2 2 2 2 2
2
2 2
1 2
1 1 5 5

Sample Output

4
We need God's help!

Hit

In the first case, Celica goes to (4,1) in turn 1. Then he goes to (4,2) in turn 2. After he gets (4,2), kill the monster 1. He goes through (4,3)->(4,4)>(3,4)->(3,5) in turn 3. At last he goes (2,5)->(1,5) in turn 4.

 

題意:從起點走到終點要走幾回合,體力耗完即開始下一回合,走進怪獸的區域體力立馬變0,碰見怪獸立即殺死,然後改怪獸所控制的領域變為可走。

分析:這題著實很多坑點,一不小心進坑了;

 

1)每一個回合, Celica 的初始行動值為L, 沒移動一個位置,行動值-1, 當行動值減為0, 則開始下一個回合 2)一旦踏入怪的所在位置,則立即會將怪殺死,怪所控制的位置也就變為0了 3)當移動到一個怪所控制的位置,行動立即減為0 4)每到達一個位置,首先變化的是行動值, 這就意味著,如果踏入一個怪所在的位置,而且該位置是被怪所控制的情況下,那麼行動值先變為0,再將怪殺死 5)怪不一定在它控制的位置 6)起點一定沒有怪, 但可能被某一個怪控制
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))

int n,m,l,k;
int sx,sy,ex,ey;
int mat[55][55],ms[55][55];
bool vis[55][55][32];//三維標記,狀態壓縮存儲怪物被殺情況
int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};

struct node
{
    int x,y;
    int ans,t,flag;
    node(){}//不這樣會棧溢出,雖然我也不知道為什麼這樣,反正我是溢出了
    node(int x, int y, int ans, int t, int flag):x(x), y(y), ans(ans), t(t), flag(flag){}
    bool friend operator < (const node &a, const node &b)
    {
        if(a.ans != b.ans) return a.ans > b.ans;
        return a.t < b.t;
    }
};
void bfs()
{
    priority_queue q;
    node now;
    vis[sx][sy][0]=true;
    q.push(node(sx, sy, 0, l, 0));
    while(!q.empty())
    {
        now=q.top();
        q.pop();

        if(now.x==ex&&now.y==ey)
        {
            if(now.t!=l)now.ans++;
            cout<n||y<=0||y>m) continue;
            if(mat[x][y]==-1) continue;

            int t=now.t-1;
            int flag=now.flag;

            if(mat[x][y]!=0)
            {
                int re=mat[x][y];
                if(!(now.flag & (1<<(re-1))))//判斷怪物是否被殺死
                    t=0;
            }
            if(ms[x][y]>=0)//怪物所在位置
                flag = now.flag | (1<<(ms[x][y]));

            if(vis[x][y][flag]) continue;
            int ans=now.ans;
            if(t==0)//體力耗盡,開始下一回合
            {
                t=l;
                ans++;
            }
            //cout<<--<>n>>m>>l)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin>>mat[i][j];
        cin>>k;
        CL(ms, -1);
        for(int i=0; i>a>>b;
            ms[a][b]=i;
        }
        cin>>sx>>sy>>ex>>ey;

        if(sx==ex&&sy==ey)//起點和終點重合的情況
        {
            cout<<0<

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved