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

BFS解决~~0~16ms~~

Posted by Sinit at 2016-12-27 12:07:40 on Problem 2386
#include<cstdio>
#include<queue>
using namespace std;
char maze[105][105];
typedef pair<int, int> P;
P p;
queue<P> que;
int main()
{
	int m, n, i, j, k, t, x, y, nx, ny, ans;
	while( scanf("%d%d", &m, &n) != EOF )
	{
		for( i=0; i<m; i++)
				scanf("%s", maze[i]);
		for( k=0, ans=0; k<m; k++)
			for( t=0; t<n; t++)
				if( maze[k][t] == 'W' )
				{
					que.push(P(k, t)), maze[k][t] = '.';
					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 && ny >=0 && nx < m && ny < n )
								{
									if( maze[nx][ny] == 'W' ) que. push(P(nx, ny));
								 	maze[nx][ny] = '.';			
								}
							}
					}
					ans++;
				}
		printf("%d\n", ans);
	}
	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