| ||||||||||
| 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 | |||||||||
深搜+广搜,1A,贴代码#include<stdio.h>
#include<memory.h>
int p,q;
char field[41][41];
int visited[41][41];
int bx,by,ex,ey;
int direct[4][2] = {{-1,0},{0,-1},{1,0},{0,1}}; //left,up.right,down
int cur_dir;
int left_num = 0,right_num = 0;
int s_path = 0;
void dfs_left(int x,int y)
{
if(field[x][y] == 'E')
return;
int t_cur,tx,ty;
for(int i = -1 ; i <= 2 ; i ++)
{
t_cur = (cur_dir + i + 4) % 4;
tx = x + direct[t_cur][0];
ty = y + direct[t_cur][1];
if(tx < 0 || tx >= p || ty < 0 || ty >= q)
continue;
if((field[tx][ty] == '.' || field[tx][ty] == 'E'))
break;
}
cur_dir = t_cur;
left_num ++;
dfs_left(tx,ty);
}
void dfs_right(int x,int y)
{
if(field[x][y] == 'E')
return;
int t_cur,tx,ty;
for(int i = 1 ; i >= -2 ; i --)
{
t_cur = (cur_dir + i + 4) % 4;
tx = x + direct[t_cur][0];
ty = y + direct[t_cur][1];
if(tx < 0 || tx >= p || ty < 0 || ty >= q)
continue;
if((field[tx][ty] == '.' || field[tx][ty] == 'E'))
break;
}
cur_dir = t_cur;
right_num ++;
dfs_right(tx,ty);
}
struct Node
{
Node(){}
Node(int xx,int yy)
{
x = xx;
y = yy;
}
int x,y;
};
Node node[1601];
void bfs()
{
int head = 0,tail = 0;
node[tail ++] = Node(bx,by);
visited[bx][by] = 0;
while(head != tail)
{
Node t = node[head ++];
head = head % 1600;
for(int i = 0 ; i < 4 ; i ++)
{
int xx = t.x + direct[i][0];
int yy = t.y + direct[i][1];
if(xx < 0 || xx >= p || yy < 0 || yy >= q || field[xx][yy] == '#')
continue;
if(visited[xx][yy] == -1)
{
visited[xx][yy] = visited[t.x][t.y] + 1;
node[tail ++] = Node(xx,yy);
if(xx == ex && yy == ey)
return;
}
}
}
}
int main()
{
int test;
scanf("%d",&test);
for(int i = 0 ; i < test ; i ++)
{
memset(visited,-1,sizeof(visited));
scanf("%d%d",&p,&q);
for(int j = 0 ; j < q ; j ++)
{
while(getchar() != '\n');
for(int k = 0 ; k < p ; k ++)
{
scanf("%c",&field[k][j]);
if(field[k][j] == 'S')
{
bx = k;
by = j;
if(bx == 0)
cur_dir = 2;
if(bx == p - 1)
cur_dir = 0;
if(by == 0)
cur_dir = 3;
if(by == q - 1)
cur_dir = 1;
}
if(field[k][j] == 'E')
{
ex = k;
ey = j;
}
}
}
int t = cur_dir;
left_num = 0;
dfs_left(bx,by);
left_num ++;
printf("%d ",left_num);
cur_dir = t;
right_num = 0;
dfs_right(bx,by);
right_num ++;
printf("%d ",right_num);
bfs();
printf("%d\n",visited[ex][ey] + 1);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator