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

迷宫类的问题,队列解法~~~大神指教

Posted by Sinit at 2016-12-25 22:59:03 on Problem 1111
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
char maze[25][25];
bool flag[25][25];
typedef pair<int, int> P;
int main()
{
	int m, n, sx, sy, x, y, nx, ny, i, j, len;
	P p;
	queue<P> que;
	while( scanf("%d%d%d%d", &m, &n, &sx, &sy) != EOF && m )
	{
		sx--, sy--;
		for( i=0; i<m; i++)
		{
			scanf("%s", maze[i]);
			for( j=0; j<n; j++)
				flag[i][j] = false;
		}
		if( maze[sx][sy] == '.' ) 
		{ 
			printf("0\n");
			continue;
		}
		que.push(P(sx, sy)), flag[sx][sy] = true, len = 0;//将起点压入队列,并标记“浏览过” 
		while( que.size() )
		{
			p = que.front(), que.pop();//取出队首元素,并删除 
			x = p.first, y = p.second;
			for( i=-1; i<=1; i++)
				for( j=-1; j<=1; j++)//访问取出点周围得点 
				{
					nx = x + i, ny = y + j;
					if( nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 'X' && !flag[nx][ny] )
						que.push(P(nx, ny)), flag[nx][ny] = true;
					else if( (maze[nx][ny] == '.' || nx < 0 || ny < 0 || nx >= m || ny >= n) && i*j == 0 ) len++;
					//只有上下左右为'.'或越出边界时,长度加一 
				}
		}
		printf("%d\n", len);
	}
	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