| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:记忆化搜索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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator