题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1242

题目描述

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel’s friends want to save Angel. Their task is: approach Angel. We assume that “approach Angel” is to get to the position where Angel stays. When there’s a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

思路

这题是求最r到a的最短路,我用DFS做超时了…

诶,还是老老实实地用BFS吧,考虑到到达’x’格子时,时间+2,到达’.’格子时,时间+1,要想时间(路径)最短,应该优先处理时间短的格子.用到优先队列.

TLE代码(DFS)

/*************************************************************************
    > File Name: 1242.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Sun 17 May 2015 11:44:30 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

char Map[205][205]; // 储存地图信息
int direct[][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // 搜索方向
int N, M; // 地图宽高
int ri, rj, ai, aj;  // 起点终点
int mint = 1<<30; // 存放最短时间(路径)
void DFS(int ri, int rj, int t) { 
    if(ri<1 || ri>N || rj<1 || rj>M) // 越界回溯
        return;
    if(t >= mint) // 超过已知最少时间回溯
        return;
    if(ri == ai && rj == aj) { // 到达终点
        if(mint > t)
            mint = t; // 更新最短时间
        return;
    }

    for(int k=0; k<4; ++k) { // 按四个方向搜索
        int di = ri+direct[k][0];
        int dj = rj+direct[k][1];
        if(Map[di][dj] != '#') { // 可走
            if(Map[di][dj] == 'x') { 
                Map[di][dj] = '#';
                DFS(di, dj, t+2); // 深搜
                Map[di][dj] = 'x';
            }
            else if(Map[di][dj] == '.') {
                Map[di][dj] = '#';
                DFS(di, dj, t+1); // 深搜
                Map[di][dj] = '.';
            }
        }
    }
}

int main()
{
#ifdef Oj
    freopen("1242.data", "r", stdin);
#endif
    while(cin >> N >> M) {
        for(int i=1; i<=N; ++i)
            for(int j=1; j<=M; ++j) {
                cin >> Map[i][j];
                if(Map[i][j] == 'r') {
                    ri = i;
                    rj = j;
                }
                else if(Map[i][j] == 'a') {
                    ai = i;
                    aj = j;
                }
            }
        Map[ri][rj] = '#'; // 起点不能回溯
        Map[ai][aj] = '.'; // 终点可访问
        mint = 1<<30;
        DFS(ri, rj, 0);
        cout << mint << endl;
    }
    return 0;
}

AC代码(BFS)

/*************************************************************************
    > File Name: 1242_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Sun 17 May 2015 20:20:30 PM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

char Map[205][205]; // 存放地图信息
int direct[][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // 搜索方向
int N, M; // 地图宽高
int ri, rj, ai, aj; // 起点r,终点a
struct node{ // node存放格子信息
    int i, j, step;  // 格子坐标,步数(时间)
    friend bool operator<(const node &a, const node &b) { // 重载<,设置优先级,步数小的先处理
        return a.step > b.step;
    }
};

int BFS(int ri, int rj) {
    priority_queue<node> Queue; // 优先队列
    node q, s; // q为当前格子,s为下一步要探索的格子
    q.i = ri;
    q.j = rj;
    q.step = 0;
    Queue.push(q); 
    while(!Queue.empty()) {
        q = Queue.top();
        Queue.pop();
        if(q.i == ai && q.j == aj) // 到终点了就返回步数(最小)
            return q.step;
        for(int k=0; k<4; ++k) {
            s.i = q.i + direct[k][0];
            s.j = q.j + direct[k][1];
            if(Map[s.i][s.j] != '#' && s.i >=1 && s.i <=N && s.j >=1 && s.j <=M) {
                if(Map[s.i][s.j] == '.'){ // 下一个格子是'.',步数+1
                    s.step = q.step + 1;
                    Queue.push(s);
                }
                else if(Map[s.i][s.j] == 'x') { // 下一个格子是'x',步数+2
                    s.step = q.step + 2;
                    Queue.push(s);
                }
                Map[s.i][s.j] = '#'; // 标记已探索过的格子
            }
        }
    } 
    return -1; // 未能找到终点
}


int main()
{
#ifdef Oj
    freopen("1242.data", "r", stdin);
#endif
    while(cin >> N >> M) {
        for(int i=1; i<=N; ++i)
            for(int j=1; j<=M; ++j) {
                cin >> Map[i][j];
                if(Map[i][j] == 'r') {
                    ri = i;
                    rj = j;
                }
                else if(Map[i][j] == 'a') {
                    ai = i;
                    aj = j;
                }
            } 
        Map[ri][rj] = '#'; // 设置起点,不能回到起点
        Map[ai][aj] = '.'; // 设置终点可访问
        int step = BFS(ri, rj); // 开始广搜
        if(step == -1)
            puts("Poor ANGEL has to stay in the prison all his life.");
        else
            cout << step << endl;
    }
    return 0;
}