[数据结构与算法]蓝桥杯 试题 算法提高 怪物森林（二分答案）

题目链接


使用二分答案法，check的时候使用bfs，但是后30分的测试点java会超内存，c++会超时，暂时还没想到满分方法qwq
破案了，把cin换成scanf C++就不会超时了。
java70分

import java.util.*;
//广度优先搜索可行是因为进入队列的每一层点都是从上一层转移过来的
//也就是一定是满足条件且能到达的
//让他直接求路中最小值的最大值不太行
//但是让他判断是可以的，因为层之间不需要关心是这一层的谁能把下一层的某个点加进来
//但是下一层的某个点一定是能到的
//BFS的好处就是每个结点都只会入队一次，节省空间和时间
//不过我觉得check函数应该用dfs也是可以的，毕竟只需要找出一条，而不是判断所有的状态，不过bfs都过不了，dfs还是算了吧...
class Pos{
	public int x;
	public int y;
	public Pos(int xx,int yy) {
		x=xx;
		y=yy;
	}
}
public class Main{
	public static int N,M;
	public static long[][] G=new long[805][805];
	public static int[][] dir= {{0,1},{0,-1},{1,0},{-1,0}};
	public static boolean check(long mid) {
		Pos s=new Pos(1,1);
		boolean[][] vis=new boolean[805][805];
		for(int i=0;i<805;i++) {
			Arrays.fill(vis[i], false);
		}
		
		LinkedList<Pos> Q=new LinkedList<Pos>();
		if(G[1][1]>=mid) {
			vis[1][1]=true;
			Q.addLast(s);
		}
		while(!Q.isEmpty()) {
//			System.out.println(Q.size());
			Pos t=Q.removeFirst();
			for(int i=0;i<4;i++) {
				int x=t.x+dir[i][0];
				int y=t.y+dir[i][1];
				if(x<1 || x>N || y<1 || y>M || vis[x][y] || G[x][y]<mid) {
					continue;
				}
				vis[x][y]=true;
				Q.addLast(new Pos(x,y));
			}
		}
		return vis[N][M];
	}
	public static void main(String[] Args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		long left=Long.MAX_VALUE,right=Long.MIN_VALUE;
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				G[i][j]=sc.nextLong();
				left=Math.min(left, G[i][j]);
				right=Math.max(right, G[i][j]);
			}
		}
		long ans=Long.MIN_VALUE;//记录过程中的答案
		while(left<=right) {
			long mid=left+(right-left)/2;
//			System.out.println(mid);
			if(check(mid)) {
				ans=mid;
				left=mid+1;
			}else {
				right=mid-1;
			}
		}
		System.out.print(ans);
	}
}

C++ 100

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Pos
{
    int x;
    int y;
    Pos(int xx,int yy)
    {
        x=xx;
        y=yy;
    }
};
int N,M;
long G[805][805];
int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
bool check(long mid)
{
    Pos s=Pos(1,1);
    bool vis[805][805];
    for(int i=0; i<805; i++)
    {
        for(int j=0;j<805;j++)
            vis[i][j]=false;
    }
    
    queue<Pos> Q;
    if(G[1][1]>=mid)
    {
        vis[1][1]=true;
        Q.push(s);
    }
    while(!Q.empty())
    {
//			System.out.println(Q.size());
        Pos t=Q.front();
        Q.pop();
        for(int i=0; i<4; i++)
        {
            int x=t.x+dir[i][0];
            int y=t.y+dir[i][1];
            if(x<1 || x>N || y<1 || y>M || vis[x][y] || G[x][y]<mid)
            {
                continue;
            }
            vis[x][y]=true;
            Q.push(Pos(x,y));
        }
    }
    return vis[N][M];
}
int main()
{
    cin >> N >> M;
    long left=0x3f3f3f3f,right=-0x3f3f3f3f;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            scanf("%lld",&G[i][j]);
            left=min(left, G[i][j]);
            right=max(right, G[i][j]);
        }
    }
    long ans=0;//记录过程中的答案
    while(left<=right)
    {
        long mid=left+(right-left)/2;
//			System.out.println(mid);
        if(check(mid))
        {
            ans=mid;
            left=mid+1;
        }
        else
        {
            right=mid-1;
        }
    }
    cout << ans;
    return 0;
}

也记录一下指环BFS+优先队列的做法

#include <bits/stdc++.h>
#define int long long
using namespace std;
int mp[805][805], n, m;
bool vis[805][805];
struct node {
 int x, y, w;
 bool operator< (const node& o) const {
  return mp[x][y] < mp[o.x][o.y];
 }
};
priority_queue<node> q;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int ans = -0x3f3f3f3f;
void bfs() {
 node start = {1, 1, mp[1][1]};
 vis[1][1] = 1;
 q.push(start);
 while(q.size()) {
  node now = q.top(); q.pop();
  if(now.x == n && now.y == m) {
   ans = max(ans, now.w);
   continue;
  }
  for(int i = 0; i < 4; i++) {
   int nx = now.x + dir[i][0], ny = now.y + dir[i][1];
   if(vis[nx][ny] || nx > n || nx < 1 || ny > m || ny < 1) continue;
   vis[nx][ny] = 1;
   q.push({nx, ny, min(now.w, mp[nx][ny])});
  }
 }
}
signed main() {
 cin >> n >> m;
 for(int i = 1; i <= n; i++) {
  for(int j = 1; j <= m; j++) {
   cin >> mp[i][j];
  }
 }
 bfs();
 cout << ans;
 return 0;
}

java版本BFS+优先队列，其实这就类似于用的启发式搜索了，每次选好的结点进行拓展。

import java.util.*;
class Pos{
	public int x,y,w;
	public Pos(int xx,int yy,int ww) {
		x=xx;
		y=yy;
		w=ww;
	}
}
public class Main{
	public static int[][] G=new int[805][805];
	public static int[][] dir= {{0,1},{0,-1},{1,0},{-1,0}};
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N,M;
		N=sc.nextInt();
		M=sc.nextInt();
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				G[i][j]=sc.nextInt();
			}
		}
		boolean[][] vis=new boolean[805][805];
		for(int i=0;i<805;i++) {
			Arrays.fill(vis[i], false);
		}
		PriorityQueue<Pos> Q=new PriorityQueue<Pos>(new Comparator<Pos>() {//改为大根堆的写法和让数组从大到小排列是一样的
			public int compare(Pos a,Pos b) {
				return b.w-a.w;
			}
		});
		vis[1][1]=true;
		Q.add(new Pos(1,1,G[1][1]));
		int ans=0;
		while(!Q.isEmpty()) {
			Pos t=Q.element();
			Q.poll();
			if(t.x==N && t.y==M) {
				ans=t.w;
				break;
			}
			for(int i=0;i<4;i++) {
				int xx=t.x+dir[i][0];
				int yy=t.y+dir[i][1];
				if(vis[xx][yy] || xx<1 || xx>N || yy<1 || yy>M) {
					continue;
				}
				vis[xx][yy]=true;
				Q.add(new Pos(xx,yy,Math.min(t.w, G[xx][yy])));
			}
			
		}
		System.out.println(ans);
	}
}

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读