题解

相似题目:滑雪
这道题可以遍历每一个点并都进行bfs
因为说是小于等于,所以标记数组可以不开,只要能规避上个数字与这个数字相等导致的重复入队就行
代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
struct ge{//结构体格子
    int nx,ny,px,py;//n开头的是储存当前节点xy,p是储存上一个节点xy(规避数字相同)
};
int h[1005][1005]={},n,m,cnt=0;//初始化
int nx[4]={0,0,1,-1},ny[4]={1,-1,0,0};//方向数组
void bfs(int x,int y){
    queue<ge>q;//队列初始化
    q.push({x,y,x,y});
    int xx,yy,px,py,f=0,f1=0;//初始化
    while (!q.empty()){
        xx=q.front().nx;
        yy=q.front().ny;
        px=q.front().px;
        py=q.front().py;//取值
        q.pop();//弹出
        if (f&&f1){break;}//如果两个海都可以到,可以提前结束循环
        if (xx==n||yy==m)f=1;//判断大西洋
        if (xx==1||yy==1)f1=1;//判断太平洋
        for (int i=0;i<4;i++){
            int wx=xx+nx[i],wy=yy+ny[i];
            if (wx>0&&wx<=n&&wy>0&&wy<=m&&!(wx==px&&wy==py)&&h[wx][wy]<=h[xx][yy]){//前面四个正常判断边界，第五个判断是否与上一个节点处于相同位置(规避等于情况)，第六个判断小于等于
                q.push({wx,wy,xx,yy});
            }
        }
    }
    if (f&&f1)cnt++;//都能走到计数加一
    return;
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>h[i][j];
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            bfs(i,j);//遍历每个点进行bfs
        }
    }
    cout<<cnt;
	return 0;
}