2014
02-17

# Dogs

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 ).

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.

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.

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

0 0

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


#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int vis[1001][1001],n,m,si,sj,ei,ej,ans;
char g[1001][1001];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct state
{
int x,y,cnt;
state(int _x=0,int _y=0,int _cnt=0):x(_x),y(_y),cnt(_cnt){};
friend bool operator <(const state &a,const state &b)
{
return a.cnt>b.cnt;
}
};
priority_queue<state> Q;
void BFS()
{
Q.push(state(si,sj,0));
vis[si][sj]=0;
state tmp;
while(!Q.empty())
{
tmp=Q.top();
Q.pop();
if(tmp.x==ei && tmp.y==ej)
{
ans=tmp.cnt;
return ;
}
for(int k=0;k<4;k++)
{
int i=tmp.x+dir[k][0];
int j=tmp.y+dir[k][1];
int t;
if(i>n || i<1|| j>m || j<1)
continue;
if(g[i][j]=='X')
t=tmp.cnt;
else t=tmp.cnt+1;
if(vis[i][j]>t)
{
vis[i][j]=t;
Q.push(state(i,j,t));
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)==2 &&(n||m))
{
getchar();
for(int i=1;i<=n;i++)
{
gets(g[i]+1);
for(int j=1;j<=m;j++)
{
//scanf("%c",&g[i][j]);
vis[i][j]=INT_MAX;
}
}
scanf("%d %d",&si,&sj);
scanf("%d %d",&ei,&ej);
ans=-1;
while(!Q.empty())
Q.pop();
BFS();
printf("%d\n",ans);
}
return 0;
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。