2014
02-12

# 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。暴力的方法就不说了，可以

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;
}

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

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