<center style="color:rgb(51,51,51);font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:14px;">
Submit: 863 Solved: 149
[ Submit][ Status][ Web Board] </center>
1097: Yuchang and Zixiang ‘s maze
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 863 Solved: 149
[ Submit][ Status][ Web Board] </center>
Description
One day , Yuchang and Zixiang go out of school to find some thing interesting . But both of them is LuChi , so the miss the way easily .
“Where am I ? who am I ?” Yuchang says . “Who attack you? You must want to say .” Zixiang adds . “Don’t say that , how we get out there ? I want my mom 555555……” Yuchang started crying . Zixiang become very panic . He doesn’t know how to get out there.
Now , they find they are in a N*M maze , they are at the (a,b) point , they know they want to go to the point (c,d) , they want to finish as soon as possible, so , could you help them ?
Same as other maze , there are some point has boom , means they can’t get the point . Give you N,M and Num (the number of points that have booms . ) , then , Num lines contains pairs (x,y) means point (x,y) have booms . then , one line contains a , b , c , d ,the begin and end point .
They can mov forward , back , left and right . And every move cost 1 second . Calculate how many seconds they need to get to the finish point .
Input
The first line contains tow numbers N,M (0 < x,y < 1000)means the size of the maze.
The second line contains a number Num (0 < N < X*Y), means the number of points which have booms .
Then next N lines each contain two numbers , xi,yi , means (xi,yi) has a boom .
Output
One line , contains one number , the time they cost .
If they can’t get to the finish point , output -1 .
Sample Input
1000 1000 4
5 5
5 7
4 6
6 6
1 1 5 6
Sample Output
-1
题意:
典型的走迷宫问题。
小地图(200*200一下)BFS、DFS都可以。大地图的话,因为信息量很大所以用不了DFS会妥妥地T掉,只能用BFS。
代码:
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1001;
const int INF=8000000;
int save[maxn][maxn];
int d[maxn][maxn];
int ex,ey;
int sx,sy;
int move_x[4]={0,0,1,-1};
int move_y[4]={1,-1,0,0};
int n,m;
int bfs(){
queue<pair<int, int> > que;
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
d[i][j]=INF;
}
}
que.push(make_pair(sx, sy));
d[sx][sy]=0;
while(que.size()){
pair<int, int> q=que.front();
que.pop();
if(q.first==ex&&q.second==ey){
return d[q.first][q.second];
}
for(i=0;i<4;i++){
int dx=q.first+move_x[i];
int dy=q.second+move_y[i];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&save[dx][dy]!=1&&d[dx][dy]==INF){
que.push(make_pair(dx, dy));
d[dx][dy]=d[q.first][q.second]+1;
}
}
}
return INF;
}
int main(){
while(~scanf("%d%d",&n,&m)){
int num;
memset(save,0,sizeof(save));
scanf("%d",&num);
while(num--)
{
int x1,y1;
scanf("%d%d",&x1,&y1);
save[x1][y1]=1;
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
int result=bfs();
if(result==INF){
printf("-1\n");
}else{
printf("%d\n",result);
}
}
return 0;
}
/**************************************************************
Problem: 1097
User: 2016_hhu09
Language: C++
Result: Accepted
Time:1323 ms
Memory:9336 kb
****************************************************************/