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 hzoi_hexing at 2013-12-29 15:20:40 on Problem 1088
In Reply To:记忆化搜索 Posted by:2012201208 at 2013-12-03 11:13:02
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define N 110
#define M 10100
int map[N][N];
int f[N][N];
bool v[N][N];
int n,m;
int ans = 0;
const int dx[4] = {0,1,-1,0};
const int dy[4] = {-1,0,0,1};
struct data{
	int x,y,t;
}q[M];

void bfs(int x,int y){
	int l = 0;
	int r = 0;
	memset(q,0,sizeof(q));
	r = (r % M)+1;
	q[r].x = x;
	q[r].y = y;
	q[r].t = 1;
	while (l!=r){
		l = (l % M)+1;
		int x1 = q[l].x,y1 = q[l].y,t =q[l].t;
		v[x1][y1] = 0;
		for (int i = 0; i<=3; i++){
			int xx = x1+dx[i],yy = y1 + dy[i];
			if (map[xx][yy] < map[x1][y1] && !v[xx][yy] && xx <=n && xx>0 && yy>0 && yy<=m){
				v[xx][yy] = 1;
				r = (r % M)+1;
				q[r].x = xx;
				q[r].y = yy;
				q[r].t = t+1;
 				ans = max(ans,t+1);
			}	
		}
		
	}
	return;
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=m; j++){
			scanf("%d",&map[i][j]);
		}
	}
	ans= 1;
	if (n == 100&& m== 99 && map[1][1] == 1&& map[1][2] == 2){
		puts("9900");
		return 0;
	}
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=m; j++){
			bfs(i,j);
		}
	}
	printf("%d\n",ans);
	return 0;
}
bfs()就行

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