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 suting at 2010-07-27 19:32:59 on Problem 1979
/*
 *	POJ1979 red and black
 *	对可以到达的黑色块进行计数 
 *	搜索策略:深度搜先搜索 
*/
#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;

#define MAXSIZE 20
char board[MAXSIZE][MAXSIZE];
int W,H; 					//棋盘的宽度和高度 
int startX,startY;			//起点坐标 
int countTitle;
//可以移动的四个方向 ,上,下,左,右
const int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

/*
void print(){
	
	int i,j;
	for( i=0 ; i<H ; i++){
		
		for(j=0; j<W; j++) 
  			cout<<board[i][j];
		cout<<endl;
	}
	cout<<endl;
}*/

bool check(int x,int y){
	
	if( x<0 || x>=H || y<0 || y>=W || '#' == board[x][y] || '0'== board[x][y]
		|| '@'== board[x][y])
		return false;
	else
		return true;
}
/*
 *	DFS搜索的核心算法 
*/
void dfsSearch(int x,int y){
	
	
	
	int i;
	int tx,ty;
	
	for(i=0;i<4;i++){
		
		tx= x+direction[i][0];
		ty= y+direction[i][1];
		
		if( check(tx,ty)){
			countTitle++;
	//		cout<<countTitle<<endl; 
			board[tx][ty]='0';
	//		print();
	//		getchar();
			dfsSearch(tx,ty);
		}
			
	}
	return ; 
}


int main(){
	
	ifstream in("test.txt");
	//初始化棋盘
	memset(board,0,sizeof(board)) ;
	countTitle=0;
	
	in>>W>>H;
	int i,j;
	for(i=0 ;i<H ; i++)
		for(j=0;j<W;j++){
			in>>board[i][j];
			if('@' == board[i][j]){
				startX=i;
				startY=j;
			}
		}
//	cout<<startX<<" "<<startY<<endl;
	clock_t time=clock();
	dfsSearch(startX,startY) ;
	cout<<"计算用时:"<<clock()-time <<"MS" <<endl;
	//起点也是计入步数的 
	cout<<countTitle+1<<endl;
} 

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