| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
dfs + bfs 关键还是 方向的确定 一次过 看我代码#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#define MAX 50
using namespace std;
struct point
{
int x , y;
int step;
};
int visit[MAX][MAX];
char maze[MAX][MAX];
int mov_left[4][2] = {{0,-1},{1,0},{0,1},{-1,0}} ; // 靠左走
int mov_righ[4][2] = {{0,1},{1,0},{0,-1},{-1,0}} ; // 靠右走
int d1 , d2 ;
int start[2];
int finish[2];
int w , h ;
int dfs(int x,int y,int d,int move[][2])
{
int step ,temp , tx , ty ;
if(x == finish[0] && y == finish[1])
return 1 ;
for(int i = 0; i < 4 ; i++)
{
temp = (d + i) % 4 ;
tx = x + move[temp][1] ;
ty = y + move[temp][0] ;
if(tx>=0 && tx<h && ty>=0 && ty<w && !visit[tx][ty])
break ;
}
step = dfs(tx,ty,(temp + 3)%4,move) + 1;
return step;
}
int bfs()
{
memset(visit,0,sizeof(visit));
queue<point> Q;
point p;
p.x = start[0] ;
p.y = start[1] ;
p.step = 1;
visit[p.x][p.y] = 1 ;
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if(p.x == finish[0] && p.y == finish[1])
return p.step ;
for(int i = 0 ; i < 4 ; i ++)
{
point temp ;
temp.x = p.x + mov_left[i][1] ;
temp.y = p.y + mov_left[i][0] ;
if(temp.x>=0 && temp.x<h && temp.y>=0 && temp.y<w && maze[temp.x][temp.y]!='#' && !visit[temp.x][temp.y])
{
visit[temp.x][temp.y] = 1;
temp.step = p.step + 1 ;
Q.push(temp) ;
}
}
}
return 0;
}
int main()
{
//freopen("in.txt","r",stdin);
int n;
cin>>n;
while(n--)
{
int i , j ;
cin>>w>>h;
memset(visit,0,sizeof(visit));
for(i = 0; i < h; i++)
{
for(j = 0; j < w; j++)
{
cin>>maze[i][j];
if(maze[i][j] == '#')
{
visit[i][j] = 1;
}
if(maze[i][j] == 'S')
{
start[0] = i ;
start[1] = j ;
}
if(maze[i][j] == 'E')
{
finish[0] = i ;
finish[1] = j ;
}
}
}
if(start[0] == 0)
{
d1 = 1 ;
d2 = 1 ;
}
else if(start[0] == h-1)
{
d1 = 3 ;
d2 = 3 ;
}
else if(start[0] == w-1)
{
d1 = 2 ;
d2 = 0 ;
}
else
{
d1 = 0 ;
d2 = 2 ;
}
cout<<dfs(start[0],start[1],d1,mov_left)<<" ";
cout<<dfs(start[0],start[1],d2,mov_righ)<<" ";
cout<<bfs()<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator