努力变强的cbx @ 2019-09-07 16:22:03
#include <iostream>
#include <algorithm>
using namespace std;
int mp[105][105], n, m, len, ans=1;
bool book[105][105], ed[105][105];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void pro(){
int i, j;
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
int a, b, c, d, e, f, g, h;
a = i+dir[0][0]; b = j+dir[0][1];
c = i+dir[1][0]; d = j+dir[1][1];
e = i+dir[2][0]; f = j+dir[2][1];
g = i+dir[3][0]; h = j+dir[3][1];
if(a>=0&&a<n&&b>=0&&b<m){
if(mp[i][j]>mp[a][b]){
ed[i][j] = true;
}
}
if(c>=0&&c<n&&d>=0&&d<m){
if(mp[i][j]>mp[c][d]){
ed[i][j] = true;
}
}
if(e>=0&&e<n&&f>=0&&f<m){
if(mp[i][j]>mp[e][f]){
ed[i][j] = true;
}
}if(g>=0&&g<n&&h>=0&&h<m){
if(mp[i][j]>mp[g][h]){
ed[i][j] = true;
}
}
}
}
}
void dfs(int x, int y, int l){
int i;
if(ed[x][y]==false){
len = max(l, len);
return;
}
for(i = 0; i < 4; i++){
int dx = x+dir[i][0];
int dy = y+dir[i][1];
if(dx<0||dx>=n||dy<0||dy>=m||book[dx][dy]){
continue;
}
if(mp[x][y]>mp[dx][dy]){
book[dx][dy] = true;
dfs(dx, dy,l+1);
book[dx][dy] = false;
}
}
return;
}
int main()
{
int i, j;
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
scanf("%d", &mp[i][j]);
}
}
pro();//预处理,找出那些“尽头”
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
if(ed[i][j]){
fill(book[0], book[0]+105*105, false);
book[i][j] = true;
dfs(i, j, 1);
ans = max(len, ans);
len = 0;
}
}
}
printf("%d", ans);
}
by Nelson_Wang @ 2019-09-07 16:29:53
这题不是记忆化搜索吗?
by 努力变强的cbx @ 2019-09-07 16:41:05
@Nelson_Wang 好,多谢dalao,我以为暴力出奇迹(其实是不会记忆化搜索)(大雾)
by junyu33 @ 2019-09-19 17:34:18
剪枝909ms
by cpphzj @ 2019-11-10 14:59:09
if (l[x][y]) return l[x][y];
这个很重要。