dfs(续做)

1.混境之地5

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dx[4]= {0,1,0,-1};
const int dy[4]= {1,0,-1,0};
int n,m,k,a,b,c,d,sign=0;
int h[1010][1010],visit[1010][1010];
void dfs(int x,int y,bool used)
{if(x==c&&y==d){sign++;return;}if(x<1||y<1||x>n||y>m||visit[x][y]){return;}for(int i=0; i<4; i++){int nx=x+dx[i];int ny=y+dy[i];if(h[nx][ny]<=h[x][y]){dfs(nx,ny,used);}else if(!used&&h[nx][ny]<=h[x][y]+k){dfs(nx,ny,true);}}
}
int main()
{memset(visit,0,sizeof(visit));cin>>n>>m>>k;cin>>a>>b>>c>>d;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cin>>h[i][j];}}dfs(a,b,false);if(sign){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return 0;
}

2.小怂爱水洼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dx[4]= {0,1,0,-1};
const int dy[4]= {1,0,-1,0};
ll n,m,sum=0,current_sum=0;
int a[110][110],visit[110][110];
void dfs(int x,int y)
{if(x<1||y<1||x>n||y>m){return;}if(visit[x][y]==1||a[x][y]==0){return;}current_sum+=a[x][y];visit[x][y]=1; for(int i=0; i<4; i++){int nx=dx[i]+x;int ny=dy[i]+y;dfs(nx,ny);	}
}
int main()
{cin>>n>>m;for(int i=1; i<=n; i++)//索引从1开始，保证nx,ny不会访问到非法地址 {for(int j=1; j<=m; j++){cin>>a[i][j];}}memset(visit,0,sizeof(visit));for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){current_sum=0;if(a[i][j]>0&&visit[i][j]!=1){dfs(i,j);sum=max(sum,current_sum);}}}cout<<sum<<endl;return 0;
}