欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

广搜之解救行动

程序员文章站 2023-12-23 19:09:57
...

广搜之解救行动

用优先级队列来存放准备扩展的结点,时间少的在队首

#include <iostream>
#include <memory.h>
#include <string>
#include <stdio.h>
#include <queue>
#include <math.h>
#include <stdlib.h>
using namespace std;
int N,M,T,BeginX,BeginY,EndX,EndY;
char Map[205][205];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int visited[205][205];
struct node
{
    int x,y,step;
    node(int xx=0,int yy=0,int ss=0):x(xx),y(yy),step(ss) {}
    friend bool operator <(const node &a, const node &b)
    {
        return a.step > b.step;
    }
};
priority_queue <node> q;
void Bfs()
{
    q.push( node( BeginX, BeginY, 0) );
    visited[BeginX][BeginY] = 1;
    while( !q.empty() )
    {
        node now = q.top();
        q.pop();
        int NowX = now.x;
        int NowY = now.y;
        int NowStep = now.step;
        if( NowX == EndX && NowY == EndY )
        {
            cout << NowStep << endl;
            return;
        }
        for( int i = 0; i < 4; i++ )
        {
            int NextX = NowX + dx[i];
            int NextY = NowY + dy[i];
            if( !visited[NextX][NextY] && Map[NextX][NextY] != '#' )
            {
                if( Map[NextX][NextY] == '@' || Map[NextX][NextY] == 'a' )
                {
                    q.push( node( NextX, NextY, NowStep + 1));
                    visited[NextX][NextY] = 1;
                }
                else if( Map[NextX][NextY] == 'x' )
                {
                    q.push( node( NextX, NextY, NowStep + 2));
                    visited[NextX][NextY] = 1;
                }
            }
        }
    }
    cout << "Impossible" << endl;
}
int main()
{
    cin >> T;
    while( T-- )
    {
        cin >> N >> M;
        memset(Map, 0, sizeof(Map));
        memset(visited, 0, sizeof(visited));
        for( int i = 1; i <= N; i++ )
            for( int j = 1; j <= M; j++ )
            {
                cin >> Map[i][j];
                if( Map[i][j] == 'r' )
                {
                    BeginX = i;
                    BeginY = j;
                }
                if( Map[i][j] == 'a' )
                {
                    EndX = i;
                    EndY = j;
                }
            }
        for( int i = 0; i <= N+1; i++ )
            for( int j = 0; j <= M+1; j++ )
                if( i==0 || j==0 || i==N+1 || j==M+1 )
                    Map[i][j] = '#';
        while( !q.empty() )
            q.pop();
        Bfs();
    }
    return 0;
}

上一篇:

下一篇: