BFS + 优先队列(hdu 2822)

Problem Description

Prairie dog comes again! Someday one little prairie dog Tim wants to visit one of his friends on the farmland, but he is as lazy as his friend (who required Tim to come to his place instead of going to Tim's), So he turn to you for help to point out how could him dig as less as he could.

We know the farmland is divided into a grid, and some of the lattices form houses, where many little dogs live in. If the lattices connect to each other in any case, they belong to the same house. Then the little Tim start from his home located at (x0, y0) aim at his friend's home ( x1, y1 ). During the journey, he must walk through a lot of lattices, when in a house he can just walk through without digging, but he must dig some distance to reach another house. The farmland will be as big as 1000 * 1000, and the up left corner is labeled as ( 1, 1 ).

 

Input

The input is divided into blocks. The first line in each block contains two integers: the length m of the farmland, the width n of the farmland (m, n ≤ 1000). The next lines contain m rows and each row have n letters, with 'X' stands for the lattices of house, and '.' stands for the empty land. The following two lines is the start and end places' coordinates, we guarantee that they are located at 'X'. There will be a blank line between every test case. The block where both two numbers in the first line are equal to zero denotes the end of the input.

 

Output

For each case you should just output a line which contains only one integer, which is the number of minimal lattices Tim must dig.

 

Sample Input

6 6
..X...
XXX.X.
....X.
X.....
X.....
X.X...
3 5
6 3
 0 0

 

Sample Output

3

Hint

Hint: Three lattices Tim should dig: ( 2, 4 ), ( 3, 1 ), ( 6, 2 ).

 

题目大意：
    有一只小狗要去找另一只小狗，两只小狗的坐标都知道，然后这个地图里只有两种元素，即房子(X)还有草地(.)，如果小狗经过房子，则不用花时间，如果经过的是草地，时间+1，最后算出小狗到达目标的时候所花费的最小时间。
因为每个节点具有的权值不一样，普通的队列只是按简单的步数，所以要用优先队列
注意m是row,n是col 

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

const int maxn = 1002;
char map[maxn][maxn];
int mark[maxn][maxn];
struct Node {
    char lattic;
    int x,y;
    int tme;
    friend bool operator < (const Node &a, const Node &b) {
        return a.tme > b.tme;
    }//时间从小到大
};

int n, m,startX,startY,endX,endY;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool Overmap(int x, int y) {
    if (x < 1 || x > m || y < 1 || y > n) {
        return true;
    }
    return false;
}

inline int BFS() {
    memset(mark, 0, sizeof(mark));
    priority_queue<Node> Q;
    Node first, next;
    first.x = startX, first.y = startY;
    first.tme = 0;
    mark[first.x][first.y] = 1;
    Q.push(first);
    while (!Q.empty())
    {
        first = Q.top();
        Q.pop();
        //找到，退出
        if (first.x == endX && first.y == endY)
        {
            //printf("find it");
            return first.tme;
        }
        //四次循环分别对应四个方向,一条直线则两个方向
        for (int i = 0; i < 4; i++)
        {
            next.x = first.x + dir[i][0];
            next.y = first.y + dir[i][1];
            //出界或者已经访问过 直接跳过下面判断
            if (Overmap(next.x, next.y) ||  mark[next.x][next.y]==1)
            {
                continue;
            }
            if (map[next.x][next.y] == 'X')
            {
                next.tme = first.tme + 0;
            }
            else
            {
                next.tme = first.tme + 1;
            }
            mark[next.x][next.y] = 1;//标志已经走过的点
            Q.push(next);//入队对它进行扩展
        }
    }
    return -1;
}

int main()
 {
    while (scanf("%d%d", &m, &n)!=EOF && m!=0 && n!=0) //用cin果断超过1000ms,用scanf512ms飘过~
    {
        for (int i = 1; i <=m; i++)
        {
            scanf("%s", map[i]+1);
        }//for(i)
        scanf("%d%d",&startX,&startY);
        scanf("%d%d",&endX,&endY);
        int res = BFS();
        printf("%d\n", res);

    }
    return 0;
}