Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

深搜+广搜,1A,贴代码

Posted by chenbwei2012 at 2014-09-01 16:24:53 on Problem 3083
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator