hdu1242 Rescue--BFS

原题链接： ​​ http://acm.hdu.edu.cn/showproblem.php?pid=1242​​

一：题意

x代表卫兵，a代表终点，r代表起始点，.代表路，#代表墙
路花费一秒，x花费两秒
问到达终点的最少时间
思路：BFS+优先队列

二：AC代码

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_Cy1_OVERLOAD_STANDARD_NAMES 1 

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;

struct Node
{
  int x, y;
  int step;
  bool operator<(const Node & node) const
  {
    return node.step < step;
  }
};

char ch[205][205];
int dis[205][205];
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
int sx, sy;//起点，也就是朋友的位置
int dx, dy;
int n, m;

bool bfs()
{
  Node t, tt;
  priority_queue<Node> pq;
  t.x = sx;
  t.y = sy;
  t.step = 0;
  pq.push(t);
  dis[sx][sy] = 0;

  while (!pq.empty())
  {
    t = pq.top();
    pq.pop();
    if (t.x == dx&&t.y == dy)
    {
      printf("%d\n", t.step);
      return true;
    }

    for (int i = 0; i < 4; i++)
    {
      tt = t;
      tt.x += dir[i][0];
      tt.y += dir[i][1];
      if (tt.x < 0 || tt.y < 0 || tt.x >= n || tt.y >= m || ch[tt.x][tt.y] == '#')
        continue;

      tt.step++;
      if (ch[tt.x][tt.y] == 'x')
        tt.step++;

      if (dis[tt.x][tt.y] >= tt.step)
      {
        dis[tt.x][tt.y] = tt.step;
        pq.push(tt);
      }
    }
  }

  return false;
}

int main() 
{
  while (~scanf("%d%d", &n, &m))
  {
    for (int i = 0; i < n; i++)
    {
      getchar();
      for (int j = 0; j < m; j++)
      {
        dis[i][j] = 99999999;
        scanf("%c", &ch[i][j]);
        if (ch[i][j] == 'a')
        {
          dx = i;
          dy = j;
        }
        else if (ch[i][j] == 'r')
        {
          sx = i;
          sy = j;
        }
      }
    }
    
    if (!bfs())
      printf("Poor ANGEL has to stay in the prison all his life.\n");
  }
  return 0;
}