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

dfs+bfs 120行

Posted by 2757585379 at 2017-07-27 10:30:19 on Problem 3083
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>

using namespace std;

const int N=50;
char maze[N][N];
int visit[N*N];
int deep[N*N];

int ans,anss, sx,sy,ex,ey,m,n;

int dir_dfs[2][4][4][2]= {{{{0,-1}, {-1,0}, {0,1}, {1,0}},
						{{-1,0}, {0,1}, {1,0}, {0,-1}},
						{{0,1}, {1,0}, {0,-1}, {-1,0}},
						{{1,0}, {0,-1}, {-1,0}, {0,1}}},

						{{{0,1}, {-1,0}, {0,-1}, {1,0}},
						{{1,0}, {0,1}, {-1,0}, {0,-1}},
						{{0,-1}, {1,0}, {0,1}, {-1,0}},
						{{-1,0}, {0,-1}, {1,0}, {0,1}}}};

int dir_bfs[4][2] = {{0,-1}, {-1,0}, {0,1}, {1,0}};

//d:当前方向
void dfs(int x, int y, int d, int step, int lr){
	if(x==ex && y==ey){
		ans = step;
		return;
	}

	for(int i=0; i<4; i++){
		int nx = x+dir_dfs[lr][d][i][0];
		int ny = y+dir_dfs[lr][d][i][1];
		if(!(nx>=0 && nx<m && ny>=0 && ny<n))
			continue;
		if(maze[nx][ny] == '#')
			continue;
		if(lr==0){
			dfs(nx, ny, (d+i+3)%4, step+1, lr);
		}else{
			if(i==0 || i==2) dfs(nx, ny, (d+i+1)%4, step+1, lr);
			else dfs(nx, ny, (d+i+3)%4, step+1, lr);
		}
		if(ans)
			return;
	}
}

void bfs(){
	memset(visit, 0, sizeof(visit));
	memset(visit, 0, sizeof(deep));
	queue<int> q;
	while(!q.empty()) q.pop();

	int sxy = sx*n+sy;
	q.push(sxy);
	visit[sxy]=1;
	deep[sxy]=1;
	while(!q.empty()){
		int t = q.front();
		q.pop();

		int x = t/n;
		int y = t%n;
		for(int i=0; i<4; i++){
			int nx = x+dir_bfs[i][0];
			int ny = y+dir_bfs[i][1];
			int nxy = nx*n+ny;
			if(!(nx>=0 && nx<m && ny>=0 && ny<n))
				continue;
			if(maze[nx][ny] == '#' || visit[nxy])
				continue;
			if(nx == ex && ny == ey){
				anss = deep[t]+1;
				return;
			}

			visit[nxy]=1;
			deep[nxy] = deep[t]+1;
			q.push(nxy);
		}
	}
}


int main(){
	//freopen ("in.txt" , "r" , stdin);
	//freopen ("out.txt" , "w" , stdout);	

	int icase;
	cin>>icase;
	while(icase--){
		cin>>n>>m;
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				cin>>maze[i][j];
				if(maze[i][j] == 'S') {sx=i;sy=j;}
				if(maze[i][j] == 'E') {ex=i;ey=j;}
			}
		}

		ans=0;
		dfs(sx,sy,0,1,0);
		cout<<ans<<" ";
		ans=0;
		dfs(sx,sy,0,1,1);
		cout<<ans<<" ";
		anss=0;
		bfs();
		cout<<anss<<endl;
	}

	return 0;
}

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