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

TLE了,哪位仁兄帮帮我看一下:

Posted by kikif at 2007-09-06 17:05:44 on Problem 3009
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

struct point{
	int x,y;
};
point cur,deln;     //cur是当前的节点位置,deln是要删除的节点

point start,end;


int w,h;      //h代表x,w代表y
int a[25][25];
int minmove;


bool isbond(int tmpx,int tmpy){
	if(tmpx<h&&tmpx>=0&&tmpy<w&&tmpy>=0){
		return true;
	}
	return false;
}



void move(int x,int y,int movenum){     //当前点的坐标
	//四个方向
	int i,j,k;
	bool find=false;
	movenum++;
	for(i=x-1;!find&&a[x-1][y]!=1;i--){ //向上滑
		if(isbond(i,y)){
			if(a[i][y]==1){
				cur.x=i+1;cur.y=y;
				deln.x=i;deln.y=y;
				find=true;    //找到了一个可以碰撞的点
			}else if(a[i][y]==3){
				if(movenum<minmove){
					minmove=movenum;
				}
				return;	
			}
		}else{
			break;
		}
	}
	if(find){
		point tmpdel=deln;
		a[tmpdel.x][tmpdel.y]=0;
		move(cur.x,cur.y,movenum);
		a[tmpdel.x][tmpdel.y]=1;
	}

	find=false;
	for(i=x+1;!find&&a[x+1][y]!=1;i++){    //向下滑
		if(isbond(i,y)){
			if(a[i][y]==1){
				cur.x=i-1;cur.y=y;
				deln.x=i;deln.y=y;
				find=true;    //找到了一个可以碰撞的点
			}else if(a[i][y]==3){
				if(movenum<minmove){
					minmove=movenum;
				}
				return;	
			}
		}else{
			break;
		}
	}
	if(find){
		point tmpdel=deln;
		a[tmpdel.x][tmpdel.y]=0;
		move(cur.x,cur.y,movenum);
		a[tmpdel.x][tmpdel.y]=1;
	}

	find=false;
	for(i=y-1;!find&&a[x][y-1]!=1;i--){  //向左滑
		if(isbond(x,i)){
			if(a[x][i]==1){
				cur.x=x;cur.y=i+1;
				deln.x=x;deln.y=i;
				find=true;    //找到了一个可以碰撞的点
			}else if(a[x][i]==3){
				if(movenum<minmove){
					minmove=movenum;
				}
				return;	
			}
		}else{
			break;
		}
	}
	if(find){
		point tmpdel=deln;
		a[tmpdel.x][tmpdel.y]=0;
		move(cur.x,cur.y,movenum);
		a[tmpdel.x][tmpdel.y]=1;
	}

	find=false;
	for(i=y+1;!find&&a[x][y+1]!=1;i++){   //向右滑
		if(isbond(x,i)){
			if(a[x][i]==1){
				cur.x=x;cur.y=i-1;
				deln.x=x;deln.y=i;
				find=true;    //找到了一个可以碰撞的点
			}else if(a[x][i]==3){
				if(movenum<minmove){
					minmove=movenum;
				}
				return;	
			}
		}else{
			break;
		}
	}
	if(find){
		point tmpdel=deln;
		a[tmpdel.x][tmpdel.y]=0;
		move(cur.x,cur.y,movenum);
		a[tmpdel.x][tmpdel.y]=1;
	}



	return;
}






void main(){
//	ifstream cin("data.txt");
	freopen("data.txt","r",stdin);
	while(1){
	//	cin>>w>>h;	
		scanf("%d%d",&w,&h);
		if(w==0)break;
		int i,j,k;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				//cin>>a[i][j];
				scanf("%d",&a[i][j]);
				if(a[i][j]==2){
					start.x=i;
					start.y=j;
				}
				if(a[i][j]==3){
					end.x=i;
					end.y=j;
				}
			}
		}
		minmove=10000;
		cur=start;
		move(cur.x,cur.y,0);
		if(minmove>10)cout<<-1<<endl;
		else cout<<minmove<<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