題干：

有一天，利姆魯在這個世界最重要的人靜被魔王帶走，并將其困在一個n*n的迷宮內(nèi)的某一處，迷宮的每個格子都可能有一只魔物，魔物的攻擊力為a[i][j]，因而利姆魯只有當攻擊力大于等于a[i][j]才能通過這個方格，否則就只能繞道（只能朝上下左右四個方向）而行。
????為了拯救靜，利姆魯決定勇闖迷宮！

????現(xiàn)在利姆魯站在（sx，sy）處，靜在（ex，ey）處，為了保證自己能夠成功拯救靜，利姆魯在初始時靠捕食者將自己的攻擊力提升到x后才出發(fā)，但是由于時間緊急（利姆魯不想和靜分開太久），使用捕食者需要花費時間，所以利姆魯想知道能夠成功救出靜的最小的x（默認初始位置的魔物對利姆魯無攻擊，即此位置對其而言是安全位置）是多少。

輸入描述:

第一行為一個正整數(shù)t（1<=t<=20)，表示測試數(shù)據(jù)的數(shù)量。 每組數(shù)據(jù)第一行為一個正整數(shù)n（1<=n<=500)，表示迷宮大小。 第2行至第n+1行，每行有n個整數(shù)，相鄰兩個數(shù)用空格隔開。第i行第j列的數(shù)a[i][j]表示這一個方格中的魔物的攻擊力大小為a[i][j]（0<=a[i][j]<=1e5)。 第n+2行為四個正整數(shù)sx，sy，ex，ey（相鄰兩個數(shù)用空格隔開），分別表示利姆魯?shù)淖鴺撕挽o的坐標。(1<=sx，sy，ex，ey<=n)。

輸出描述:

利姆魯初始的攻擊力的最小值x（大于等于0的整數(shù)）。

示例1

輸入

復制

1 5 1 2 3 4 5 1 2 3 4 7 3 4 2 1 3 7 8 1 2 3 3 1 2 3 6 1 1 5 5

輸出

復制

6

說明

其中一條使得初始攻擊力最小的路線為(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)->(5,5)，此時初始攻擊力只要6，因而答案是6。

解題報告：

? ? 二分一下需要提升的攻擊力，然后搜索check是否可以滿足就可以了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n; int sx,sy,ex,ey; int mid; bool flag; int a[555][555]; bool vis[555][555]; int nx[4] = {0,1,0,-1}; int ny[4] = {1,0,-1,0}; bool ok(int x,int y) {if(x>=1 && x<=n && y>=1 && y<=n) return 1;else return 0; } void dfs(int x,int y) {if(x == ex && y == ey) {flag = 1;return;}for(int k = 0; k<4; k++) {int tx = x + nx[k];int ty = y + ny[k];if(ok(tx,ty) == 0) continue;if(a[tx][ty] > mid) continue;if(vis[tx][ty]) continue;vis[tx][ty] = 1;dfs(tx,ty);if(flag) return;}} int main() {int t;cin>>t;while(t--) {scanf("%d",&n);int maxx = 0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {scanf("%d",&a[i][j]);maxx = max(maxx,a[i][j]);}}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);int l = a[ex][ey],r = maxx;mid = (l+r)>>1;int ans = 0;/如果不加=0？ while(l<=r) {mid = (l+r)>>1;memset(vis,0,sizeof vis);vis[sx][sy] = 1;flag = 0;dfs(sx,sy);if(flag) r = mid-1, ans = mid;else l = mid+1;}printf("%d\n",ans);}return 0 ;}

不加=0也可以AC，，說明數(shù)據(jù)保證有解了。

這題也可以用類似并查集的東西，就是先把二維坐標變成線性的，然后并查集：把值為a[i][j]的push_back到對應的vector中，然后從小到大枚舉答案一直到起點和終點被并到同一個集合中，結(jié)束程序。

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second #define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++) #define REP(I, N) for (int I = 0; I < (N); ++I) using namespace std; const int SIZE = 1e5+10; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<ll> VL; typedef vector<PII> VPII; struct Union_Find {int d[250001],num[250001];void init(int n) {REP(i,n)d[i]=i,num[i]=1;}int find(int x) {return (x!=d[x])?(d[x]=find(d[x])):x;}bool is_root(int x) {return d[x]==x;}bool uu(int x,int y) {x=find(x);y=find(y);if(x==y)return 0;if(num[x]>num[y])swap(x,y);num[y]+=num[x];d[x]=y;return 1;} } U; VPII pp[SIZE]; int a[555][555]; int dx[4]= {1,0,-1,0}; int dy[4]= {0,1,0,-1}; int main() {CASET {int n;cin>>n;U.init(n*n);REP(i,SIZE)pp[i].clear();REP(i,n)REP(j,n) {scanf("%d",&a[i][j]);pp[a[i][j]].pb({i,j});}PII st,ed;scanf("%d%d",&st.fi,&st.se);scanf("%d%d",&ed.fi,&ed.se);st.fi--;st.se--;ed.fi--;ed.se--;a[st.fi][st.se]=0;pp[0].pb(st);REP(i,SIZE) {for(auto p:pp[i]) {REP(j,4) {int nx=p.fi+dx[j];int ny=p.se+dy[j];if(nx<0||ny<0||nx>=n||ny>=n)continue;if(a[nx][ny]<=i)U.uu(p.fi*n+p.se,nx*n+ny);}}if(U.find(st.fi*n+st.se)==U.find(ed.fi*n+ed.se)) {printf("%d\n",i);break;}}}return 0; }

還有一種方法：

優(yōu)先隊列維護權(quán)值小根堆，然后bfs整張地圖一次，同時權(quán)值遞增的同時維護最大值，也就是如果一條路是1->3->2，那整2那個地方的權(quán)值也是3。大概是這個意思。

#include<bits/stdc++.h> using namespace std; const int N=505; struct node{int x,y,g;bool friend operator<(node c,node d){return c.g>d.g;} }no,ne; int a[N][N],n,sx,sy,ex,ey,m[4][2]={1,0,-1,0,0,1,0,-1}; bool vis[N][N]; void bfs(){memset(vis,0,sizeof(vis));priority_queue<node>q;no.x=sx;no.y=sy;no.g=0;vis[no.x][no.y]=1;q.push(no);while(!q.empty()){no=q.top();q.pop();if(no.x==ex&&no.y==ey){printf("%d\n",no.g);return;}for(int i=0;i<4;i++){ne.x=no.x+m[i][0];ne.y=no.y+m[i][1];if(ne.x<1||ne.x>n||ne.y<1||ne.y>n||vis[ne.x][ne.y])continue;ne.g=max(no.g,a[ne.x][ne.y]);vis[ne.x][ne.y]=1;q.push(ne);}} } int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);scanf("%d%d%d%d",&sx,&sy,&ex,&ey);bfs();} }

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 318F】关于我转生变成史莱姆这档事（二分，搜索）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。