Kanoshuuya @ 2019-08-01 15:28:13
#include <bits/stdc++.h>
using namespace std;
struct point{
int x,y;
int val;
int step;
}p[101][101];
int r,c;
int dx[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
int Max = -1;
int isOK(int x,int y){
if(x>=0&&x<r&&y>=0&&y<c) return 1;
else return -1;
}
void bfs(int x,int y){
queue<point> q;
q.push(p[x][y]);
while(q.size()>0){
point n = q.front();
q.pop();
for(int i=0;i<4;i++){
int xx = n.x+dx[i][0];
int yy = n.y+dx[i][1];
if(p[xx][yy].val<n.val&&isOK(xx,yy)==1){
p[xx][yy].step = max(n.step + 1,p[xx][yy].step);
Max = max(p[xx][yy].step,Max);
q.push(p[xx][yy]);
}
}
}
}
int main()
{
cin>>r>>c;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++){
cin>>p[i][j].val;
p[i][j].x = i;
p[i][j].y = j;
p[i][j].step = 1;
}
for(int i=0;i<r;i++)
for(int j=0;j<c;j++){
if(p[i][j].step==1)
bfs(i,j);
}
if(Max>0)
cout<<Max<<endl;
else
cout<<1;
return 0;
}
用的是BFS,不知道还有没有救
by Lacrymabri @ 2019-08-03 17:18:59
开o2优化就能过了(我也不知道为什么,可能stl的模板类比较慢吧)
by Neptune0 @ 2019-08-04 18:38:20
我觉得楼主这个暴搜不行是因为
这是个暴搜嘛 建议用记忆化深搜。
by Kanoshuuya @ 2019-08-05 15:30:35
@Lacrymabri
开了o2依然TLE
可能还是得用DFS剪枝吧
by Kanoshuuya @ 2019-08-05 15:31:40
@Neptune0
一开始用了BFS不想改DFS
我去试试
by Lacrymabri @ 2019-08-09 15:09:42
@Kanoshuuya 我也用的是bfs,也是第二组TLE,加了o2就过了(逃)