做百度网站如何收费,网络公司可以做哪些业务,公司注册流程步骤,杭州专业建设网站哪里好题干#xff1a; 有一天#xff0c;利姆鲁在这个世界最重要的人静被魔王带走#xff0c;并将其困在一个n*n的迷宫内的某一处#xff0c;迷宫的每个格子都可能有一只魔物#xff0c;魔物的攻击力为a[i][j]#xff0c;因而利姆鲁只有当攻击力大于等于a[i][j]才能通过这个方…题干 有一天利姆鲁在这个世界最重要的人静被魔王带走并将其困在一个n*n的迷宫内的某一处迷宫的每个格子都可能有一只魔物魔物的攻击力为a[i][j]因而利姆鲁只有当攻击力大于等于a[i][j]才能通过这个方格否则就只能绕道只能朝上下左右四个方向而行。 为了拯救静利姆鲁决定勇闯迷宫 现在利姆鲁站在sxsy处静在exey处为了保证自己能够成功拯救静利姆鲁在初始时靠捕食者将自己的攻击力提升到x后才出发但是由于时间紧急利姆鲁不想和静分开太久使用捕食者需要花费时间所以利姆鲁想知道能够成功救出静的最小的x默认初始位置的魔物对利姆鲁无攻击即此位置对其而言是安全位置是多少。
输入描述:
第一行为一个正整数t1t20)表示测试数据的数量。
每组数据第一行为一个正整数n1n500)表示迷宫大小。
第2行至第n1行每行有n个整数相邻两个数用空格隔开。第i行第j列的数a[i][j]表示这一个方格中的魔物的攻击力大小为a[i][j]0a[i][j]1e5)。
第n2行为四个正整数sxsyexey相邻两个数用空格隔开分别表示利姆鲁的坐标和静的坐标。(1sxsyexeyn)。
输出描述:
利姆鲁初始的攻击力的最小值x大于等于0的整数。
示例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代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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(x1 xn y1 yn) return 1;else return 0;
}
void dfs(int x,int y) {if(x ex y ey) {flag 1;return;}for(int k 0; k4; 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;cint;while(t--) {scanf(%d,n);int maxx 0;for(int i 1; in; i) {for(int j 1; jn; 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 (lr)1;int ans 0;/如果不加0 while(lr) {mid (lr)1;memset(vis,0,sizeof vis);vis[sx][sy] 1;flag 0;dfs(sx,sy);if(flag) r mid-1, ans mid;else l mid1;}printf(%d\n,ans);}return 0 ;}
不加0也可以AC说明数据保证有解了。
这题也可以用类似并查集的东西就是先把二维坐标变成线性的然后并查集把值为a[i][j]的push_back到对应的vector中然后从小到大枚举答案一直到起点和终点被并到同一个集合中结束程序。
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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 cs1;cs___T;cs)
#define REP(I, N) for (int I 0; I (N); I)
using namespace std;
const int SIZE 1e510;
typedef pairint,int PII;
typedef vectorint VI;
typedef vectorll VL;
typedef vectorPII 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) {xfind(x);yfind(y);if(xy)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;cinn;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 nxp.fidx[j];int nyp.sedy[j];if(nx0||ny0||nxn||nyn)continue;if(a[nx][ny]i)U.uu(p.fi*np.se,nx*nny);}}if(U.find(st.fi*nst.se)U.find(ed.fi*ned.se)) {printf(%d\n,i);break;}}}return 0;
}
还有一种方法
优先队列维护权值小根堆然后bfs整张地图一次同时权值递增的同时维护最大值也就是如果一条路是1-3-2那整2那个地方的权值也是3。大概是这个意思。
#includebits/stdc.h
using namespace std;
const int N505;
struct node{int x,y,g;bool friend operator(node c,node d){return c.gd.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_queuenodeq;no.xsx;no.ysy;no.g0;vis[no.x][no.y]1;q.push(no);while(!q.empty()){noq.top();q.pop();if(no.xexno.yey){printf(%d\n,no.g);return;}for(int i0;i4;i){ne.xno.xm[i][0];ne.yno.ym[i][1];if(ne.x1||ne.xn||ne.y1||ne.yn||vis[ne.x][ne.y])continue;ne.gmax(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 i1;in;i)for(int j1;jn;j)scanf(%d,a[i][j]);scanf(%d%d%d%d,sx,sy,ex,ey);bfs();}
}
