首页 > 搜索 > BFS搜索 > hdu 2645 find the nearest station -BFS-[解题报告]C++
2014
02-12

hdu 2645 find the nearest station -BFS-[解题报告]C++

find the nearest station

问题描述 :

Since dandelion has left the hometown so long,she finds it’s difficult to find the station in the city.So she needs you ,a clear programmer, to help her.
Now you know the map of the city, which has showed every station in the city.You are asked to find the shortest distance between every grid and the stations.You should notice that the road in dandelion’s hometown is vertical or horizontal,so the distance of two girds is defined as |x1-x2|+|y1-y2|.

输入:

The input consists of several test cases. Each test case start with a line containing two number, n, m(1 <= n, m ≤ 182), the rows and the columns of city. Then n lines follow, each contain exact m characters, representing the type of block in it. (0 for empty place ,1 for station).The data will contains at least one station.

输出:

The input consists of several test cases. Each test case start with a line containing two number, n, m(1 <= n, m ≤ 182), the rows and the columns of city. Then n lines follow, each contain exact m characters, representing the type of block in it. (0 for empty place ,1 for station).The data will contains at least one station.

样例输入:

3 4
0001
0011
0110

样例输出:

3 2 1 0
2 1 0 0
1 0 0 1

/*
分析:
    水题,BFS或者暴力都行。
    竟然排第一额-、-II。暴力的方法就不说了,可以
看成一道多源点的BFS(也可以看成有一个虚拟节点为到
所有station的总源点,没什么区别),点的总数为n的
话,那么暴力要O(n^2),用BFS的话就是O(n)了。

                                                     2013-01-23
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"queue"
#define N 333
using namespace std;

int n,m;
char map[N][N];
int dis[N][N],flag[N][N];
int dir[4][2]={1,0, -1,0, 0,1, 0,-1};

struct node
{
    int x,y;
};
void solve()
{
    queue<node>q;
    node now,next;
    memset(dis,0,sizeof(dis));
    memset(flag,0,sizeof(flag));
    int i,l;
    for(i=0;i<n;i++)
    {
        scanf("%s",map[i]);
        for(l=0;l<m;l++)
        {
            if(map[i][l]=='1')
            {
                now.x=i,now.y=l;
                q.push(now);
                flag[i][l]=1;
            }
        }
    }
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x<0 || next.x>=n || next.y<0 || next.y>=m)    continue;
            if(flag[next.x][next.y])                            continue;
            q.push(next);
            flag[next.x][next.y]=1;
            dis[next.x][next.y]=dis[now.x][now.y]+1;
        }
    }
}
int main()
{
    int i,l;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        solve();
        for(i=0;i<n;i++)
        {
            printf("%d",dis[i][0]);
            for(l=1;l<m;l++)    printf(" %d",dis[i][l]);
            printf("\n");
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/ice_crazy/article/details/8535791


,
  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。