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

Re:雁过留声——后缀数组+扫描

Posted by 200831000719 at 2010-04-07 22:09:38 on Problem 1979
In Reply To:看大家都用DSF和回溯,小弟我就改成用队列来实现了,果然可以AC,呵呵~ Posted by:gfedcba at 2009-01-12 21:34:49
> // 平时用栈来模拟回溯,这里我不用栈而用队列且不回溯也不深搜
> // 如有错误之处,望大牛提点迷津,谢谢
> 
> #include <iostream>
> using namespace std;
> 
> const int N = 20;
> 
> int move[4][4]={{0,-1}, {0,1}, {-1,0}, {1,0}};
> 
> bool Place(char room[][20], int i, int j, int w, int h) // 判断当前地点是否合格
> {
> 	if (i>=0 && i<=w-1 && j>=0 && j<=h-1 && room[i][j]=='.')
> 	{
> 		return true;
> 	}
> 	else
> 	{
> 		return false;
> 	}
> 	
> }
> 
> struct Node
> {
> 	int i;
> 	int j;
> };
> 
> int main()
> {
> 	
> 	char room[N][N];
> 	Node queue[N*N]={0};
> 	int front; 
> 	int tail ;
> 	
> 	int count= 0;
>         int w, h;
> 	int i, j;
> 	int mani, manj; // 标记人开始站的地点
> 	int way; // 移动路线
> 
> 	while (cin>>h>>w && w!=0 && h!=0)
> 	{
> 		count = 0;
> 		memset(room, 0, sizeof(room));
> 		memset(queue, 0, sizeof(queue)); // 初始化时清空队列,RE过一次
> 		front = tail = 0;                // 队头队尾也要初始化,RE过一次
> 
> 		for (i=0; i<=w-1; i++)   // 处理输入
> 		{
> 			for (j=0; j<=h-1; j++)
> 			{
> 				cin>>room[i][j];
> 				if (room[i][j] =='@')
> 				{
> 					mani = i;
> 					manj = j;
> 				}
> 			}
> 		}
> 		
> 		queue[tail].i = mani; // 将人所站的地点入队
> 		queue[tail].j = manj;
> 		room[mani][manj] = '!'; // 对room进行标记
> 		tail++;
> 		count++;
> 		
> 		Node temp;
> 		while (front != tail) // 如果队列为空,则表示将一个连通的地点区域都遍历完了
> 		{
> 			temp = queue[front]; 
> 			front++;   // 出队
> 			
> 			for (way=0; way<=4-1; way++)
> 			{
> 				if (Place(room, temp.i+move[way][0], temp.j+move[way][1], w, h))
> 				{
> 					queue[tail].i = temp.i+move[way][0]; // 出队之后,将没有遍历过的地点入队
> 					queue[tail].j = temp.j+move[way][1];
> 
> 					room[queue[tail].i][queue[tail].j] = '!';
> 					tail++;
> 					count++;
> 				}
> 				
> 			}
> 		}
> 		cout<<count<<endl;
> 		
> 	}
> 	return 0;
> }
HAO DE

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