A:
bfs搜索即可，每次都对当前的数字进行所有的变换，然后记录一下状态有没有出现过，第一次遇到那个数字一定是时间最小的。
这里我的写法多次一举写了个小顶堆的bfs。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 5e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read(){ int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int dp[10][10][10][10]; int cal1(int x) { if(x == 9) return 1; else return x + 1; } int cal2(int x) { if(x == 1) return 9; else return x - 1; } struct Node{ int x1,x2,x3,x4,sum; bool operator < (const Node a) const { return sum > a.sum; } }; void bfs(int x1,int x2,int x3,int x4) { priority_queue<Node> Q; dp[x1][x2][x3][x4] = 0; Q.push(Node{x1,x2,x3,x4,0}); while(!Q.empty()) { Node q = Q.top(); int px1 = q.x1,px2 = q.x2,px3 = q.x3,px4 = q.x4; x1 = q.x1,x2 = q.x2,x3 = q.x3,x4 = q.x4; int sum = q.sum; Q.pop(); px1 = cal1(x1); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px1 = x1; px1 = cal2(x1); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px1 = x1; px2 = cal1(x2); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px2 = x2; px2 = cal2(x2); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px2 = x2; px3 = cal1(x3); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px3 = x3; px3 = cal2(x3); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px3 = x3; px4 = cal1(x4); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px4 = x4; px4 = cal2(x4); if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px4 = x4; px1 = x2,px2 = x1; if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px1 = x1,px2 = x2; px2 = x3,px3 = x2; if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px2 = x2,px3 = x3; px3 = x4,px4 = x3; if(sum + 1 < dp[px1][px2][px3][px4]) { dp[px1][px2][px3][px4] = sum + 1; Q.push(Node{px1,px2,px3,px4,sum + 1}); } px3 = x3,px4 = x4; } } int main() { int ca = read(); while(ca--) { memset(dp,0x3f3f3f,sizeof(dp)); string s1,s2; cin >> s1 >> s2; bfs(s1[0] - '0',s1[1] - '0',s1[2] - '0',s1[3] - '0'); printf("%d ",dp[s2[0] - '0'][s2[1] - '0'][s2[2] - '0'][s2[3] - '0']); } return 0; }
B：
依旧是bfs搜索，可以发现这里只有人的位置和箱子的位置在变，那么就用vis[i][j][k][m]表示当箱子的位置在i,j，人的位置在k,m时，有没有出现过这个状态。
然后注意推的时候看看人能不能走到推的那个位置，这里用dfs来搜能不能走到。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 5e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read(){ int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int a[10][10],n,m,b[4][2] = {1,0,-1,0,0,1,0,-1}; bool vis[10][10][10][10],used[10][10]; struct Node { int x,y,dis,prex,prey; bool operator < (const Node a) const { return dis > a.dis; } }; bool dfs(int x,int y,int zx,int zy,int ex,int ey) { used[x][y] = 1; if(x == ex && y == ey) return true; int ans = 0; for(int i = 0;i < 4;++i) { int px = x + b[i][0]; int py = y + b[i][1]; if(px >= 1 && px <= n && py >= 1 && py <= m && !used[px][py] && a[px][py] != 1 && (px != zx || py != zy)) { ans |= dfs(px,py,zx,zy,ex,ey); } } return ans; } int bfs(int sx,int sy,int ex,int ey,int posx,int posy) { priority_queue<Node> Q; Q.push(Node{sx,sy,0,posx,posy}); while(!Q.empty()) { Node q = Q.top(); Q.pop(); if(q.x == ex && q.y == ey) return q.dis; for(int i = 0;i < 4;++i) { int px = q.x + b[i][0]; int py = q.y + b[i][1]; int pxx = q.x - b[i][0]; int pyy = q.y - b[i][1]; if(px >= 1 && px <= n && py >= 1 && py <= m && a[px][py] != 1 && pxx >= 1 && pxx <= n && pyy >= 1 && pyy <= m && a[pxx][pyy] != 1 && !vis[px][py][pxx][pyy]) { memset(used,0,sizeof(used)); // printf("(%d,%d) peo(%d,%d) to(%d,%d) ",q.x,q.y,q.prex,q.prey,pxx,pyy); if(dfs(q.prex,q.prey,q.x,q.y,pxx,pyy)) { // printf("YES "); vis[px][py][pxx][pyy] = 1; Q.push(Node{px,py,q.dis + 1,q.x,q.y}); } else { // printf("no "); } } } } return -1; } int main() { int ca;ca = read(); while(ca--) { n = read(),m = read(); memset(vis,0,sizeof(vis)); int sx,sy,ex,ey,posx,posy; for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) a[i][j] = read(); for(int i = 1;i <= n;++i) { for(int j = 1;j <= m;++j) { if(a[i][j] == 2) sx = i,sy = j; if(a[i][j] == 3) ex = i,ey = j; if(a[i][j] == 4) posx = i,posy = j; } } printf("%d ",bfs(sx,sy,ex,ey,posx,posy)); } return 0; } /*2 5 5 0 3 0 0 0 1 0 1 4 0 0 0 1 0 0 1 1 2 0 0 0 0 0 0 0 */
C：
双向bfs搜索，因为这里要保证8步内到，且起点和终点状态都确定，那么我们就可以从起点和终点同时开始bfs，注意我们让两边的时间限制都为4，这样当一边的状态
在另一个队列出现，且时间没超过4的情况，就说明能走到，注意这里int开不出空间，所以就用char来开。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 5e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read(){ int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; struct Node { int x,y; bool operator == (const Node a) const { if(a.x == x && a.y == y) return true; else return false; } bool operator != (const Node a) const { if(a.x != x || a.y != y) return true; else return false; } }; Node a[5],b[5]; char vis[9][9][9][9][9][9][9][9]; int dir[8][2] = {1,0,-1,0,0,1,0,-1,2,0,-2,0,0,2,0,-2}; struct PP { Node p1,p2,p3,p4; int dis; PP(Node a,Node b,Node c,Node d,int x) { p1 = a,p2 = b,p3 = c,p4 = d,dis = x; } }; int check1(int x,int y,PP a) { if(x >= 0 && x < 8 && y >= 0 && y < 8 && a.dis <= 4) { if(vis[a.p1.x][a.p1.y][a.p2.x][a.p2.y][a.p3.x][a.p3.y][a.p4.x][a.p4.y] == '1') return 0; else if(vis[a.p1.x][a.p1.y][a.p2.x][a.p2.y][a.p3.x][a.p3.y][a.p4.x][a.p4.y] == '2') return 1; else { vis[a.p1.x][a.p1.y][a.p2.x][a.p2.y][a.p3.x][a.p3.y][a.p4.x][a.p4.y] = '1'; return 2; } } return 0; } int check2(int x,int y,PP a) { if(x >= 0 && x < 8 && y >= 0 && y < 8 && a.dis <= 4) { if(vis[a.p1.x][a.p1.y][a.p2.x][a.p2.y][a.p3.x][a.p3.y][a.p4.x][a.p4.y] == '2') return 0; else if(vis[a.p1.x][a.p1.y][a.p2.x][a.p2.y][a.p3.x][a.p3.y][a.p4.x][a.p4.y] == '1') return 1; else { vis[a.p1.x][a.p1.y][a.p2.x][a.p2.y][a.p3.x][a.p3.y][a.p4.x][a.p4.y] = '2'; return 2; } } return 0; } bool bfs() { queue<PP> Q1,Q2; vis[a[1].x][a[1].y][a[2].x][a[2].y][a[3].x][a[3].y][a[4].x][a[4].y] = '1'; vis[b[1].x][b[1].y][b[2].x][b[2].y][b[3].x][b[3].y][b[4].x][b[4].y] = '2'; Q1.push(PP{Node{a[1].x,a[1].y} , Node{a[2].x,a[2].y} , Node{a[3].x,a[3].y} , Node{a[4].x,a[4].y} , 0}); Q2.push(PP{Node{b[1].x,b[1].y} , Node{b[2].x,b[2].y} , Node{b[3].x,b[3].y} , Node{b[4].x,b[4].y} , 0}); while(!Q1.empty() || !Q2.empty()) { if(!Q1.empty()) { PP q = Q1.front(); Q1.pop(); for(int i = 0;i < 8;++i) { PP t = q; int px = q.p1.x + dir[i][0]; int py = q.p1.y + dir[i][1]; t.p1 = Node{px,py}; t.dis = q.dis + 1; int ma = check1(px,py,t); if(ma == 1) return true; if(ma == 2) { Q1.push(t); } } for(int i = 0;i < 8;++i) { PP t = q; int px = q.p2.x + dir[i][0]; int py = q.p2.y + dir[i][1]; t.p2 = Node{px,py}; t.dis = q.dis + 1; int ma = check1(px,py,t); if(ma == 1) return true; if(ma == 2) { Q1.push(t); } } for(int i = 0;i < 8;++i) { PP t = q; int px = q.p3.x + dir[i][0]; int py = q.p3.y + dir[i][1]; t.p3 = Node{px,py}; t.dis = q.dis + 1; int ma = check1(px,py,t); if(ma == 1) return true; if(ma == 2) { Q1.push(t); } } for(int i = 0;i < 8;++i) { PP t = q; int px = q.p4.x + dir[i][0]; int py = q.p4.y + dir[i][1]; t.p4 = Node{px,py}; t.dis = q.dis + 1; int ma = check1(px,py,t); if(ma == 1) return true; if(ma == 2) { Q1.push(t); } } } if(!Q2.empty()) { PP q = Q2.front(); Q2.pop(); for(int i = 0;i < 8;++i) { PP t = q; int px = q.p1.x + dir[i][0]; int py = q.p1.y + dir[i][1]; t.p1 = Node{px,py}; t.dis = q.dis + 1; int ma = check2(px,py,t); if(ma == 1) return true; if(ma == 2) { Q2.push(t); } } for(int i = 0;i < 8;++i) { PP t = q; int px = q.p2.x + dir[i][0]; int py = q.p2.y + dir[i][1]; t.p2 = Node{px,py}; t.dis = q.dis + 1; int ma = check2(px,py,t); if(ma == 1) return true; if(ma == 2) { Q2.push(t); } } for(int i = 0;i < 8;++i) { PP t = q; int px = q.p3.x + dir[i][0]; int py = q.p3.y + dir[i][1]; t.p3 = Node{px,py}; t.dis = q.dis + 1; int ma = check2(px,py,t); if(ma == 1) return true; if(ma == 2) { Q2.push(t); } } for(int i = 0;i < 8;++i) { PP t = q; int px = q.p4.x + dir[i][0]; int py = q.p4.y + dir[i][1]; t.p4 = Node{px,py}; t.dis = q.dis + 1; int ma = check2(px,py,t); if(ma == 1) return true; if(ma == 2) { Q2.push(t); } } } } return false; } int main() { while(~scanf("%d",&a[1].x)) { memset(vis,0,sizeof(vis)); a[1].x--; a[1].y = read() - 1; for(int i = 2;i <= 4;++i) a[i].x = read() - 1,a[i].y = read() - 1; for(int i = 1;i <= 4;++i) b[i].x = read() - 1,b[i].y = read() - 1; printf("%s ",bfs() ? "YES" : "NO"); } return 0; }
D：
这里题目的限制描述有点不太严谨，应该保证无环产生才行。
这样的话就是一棵树，那么题目问的也就是树的直径。
树的直径有一个性质：到某个点距离最远的点肯定是直径上的一个点。
那么我们就可以以1为根找到和1最远的点，肯定就是直径上的一个点。
那么再以这个点为根去找到直径上的另一个点，他们的距离就是直径了。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 4e4 + 5; const int M = 88888888; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int n,m,dp[N];//0 - xia,1 - shang struct Node{ int to,dis; }; vector<Node> G[N]; void dfs(int u,int fa,int d) { dp[u] = dp[fa] + d; for(auto v : G[u]) { if(v.to == fa) continue; dfs(v.to,u,v.dis); } } int main() { n = read(),m = read(); while(m--) { int x,y,L;x = read(),y = read(),L = read(); char c;cin >> c; G[x].push_back(Node{y,L}); G[y].push_back(Node{x,L}); } dfs(1,0,0); int mx = 0,pos = 0; for(int i = 1;i <= n;++i) { if(dp[i] > mx) { mx = dp[i]; pos = i; } } memset(dp,0,sizeof(dp)); dfs(pos,0,0); int ans = 0; for(int i = 1;i <= n;++i) { ans = max(ans,dp[i]); } printf("%d ",ans); return 0; }
E：
这题主要是卡空间和时间，因为这里说1不能移动。
那么我们把这个环看成以1开头的一个数字，且我们保证状态永远以1作为开头。
dp[x]表示1后面顺时针接数字x的最小步数。
这里1不需要记录所以最大状态就是87654321,空间和时间复杂度都压下来了。
因为我们最终都是要得到12345678，那么我们就可以一开始从12345678倒着搜，预处理出所有状态的最小步数。
预处理也是基本的bfs，要记录一下在中心的点是谁就行了。
因为我们保证了
这样询问的时候就可以O（1）输出。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 88888888; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int a[10]; int dp[8765432 + 1]; struct Node{ int x,dis,in; }; void init() { dp[2345678] = 1; queue<Node> Q; Q.push(Node{2345678,1,0}); while(!Q.empty()) { Node q = Q.front(); int c = q.x; Q.pop(); //printf("%d is %d ",c,q.dis); int pos0 = 0; for(int i = 7;i >= 1;--i) { a[i] = q.x % 10; q.x /= 10; if(a[i] == 0) pos0 = i; } //if(pos0 == 0) printf("%d is %d ",c,q.dis); if(q.in == 0) { for(int i = 1;i <= 7;++i) { int ma = 0; for(int j = 1;j <= 7;++j) { if(j == i) ma = (ma * 10 + 0); else ma = ma * 10 + a[j]; } if(dp[ma] == 0) { dp[ma] = q.dis + 1; Q.push(Node{ma,q.dis + 1,a[i]}); } } } else { int ma = 0;//in for(int i = 1;i <= 7;++i) { if(a[i] == 0) ma = (ma * 10 + q.in); else ma = (ma * 10 + a[i]); } if(dp[ma] == 0) { dp[ma] = q.dis + 1; Q.push(Node{ma,q.dis + 1,0}); } if(pos0 >= 2 && pos0 <= 6) { ma = 0;//left for(int i = 1;i <= 7;++i) { if(i == pos0 - 1) ma = (ma * 10 + 0); else if(i == pos0) ma = (ma * 10 + a[i - 1]); else ma = ma * 10 + a[i]; } if(dp[ma] == 0) { dp[ma] = q.dis + 1; Q.push(Node{ma,q.dis + 1,q.in}); } ma = 0;//right for(int i = 1;i <= 7;++i) { if(i == pos0 + 1) ma = (ma * 10 + 0); else if(i == pos0) ma = (ma * 10 + a[i + 1]); else ma = ma * 10 + a[i]; } if(dp[ma] == 0) { dp[ma] = q.dis + 1; Q.push(Node{ma,q.dis + 1,q.in}); } } else if(pos0 == 1){ ma = a[2]; ma = (ma * 10 + 0); for(int i = 3;i <= 7;++i) { ma = (ma * 10 + a[i]); } if(dp[ma] == 0) { dp[ma] = q.dis + 1; Q.push(Node{ma,q.dis + 1,q.in}); } } else { ma = 0; for(int i = 1;i <= 5;++i) { ma = (ma * 10 + a[i]); } ma = (ma * 10 + 0); ma = (ma * 10 + a[6]); if(dp[ma] == 0) { dp[ma] = q.dis + 1; Q.push(Node{ma,q.dis + 1,q.in}); } } } } } int cal(int x) { if(x == 8) return 1; else return x + 1; } int main() { init(); int ca;ca = read(); while(ca--) { int pos; for(int i = 1;i <= 8;++i) a[i] = read(); for(int i = 1;i <= 8;++i) { if(a[i] == 1) pos = i; } int i = cal(pos); int ma = a[i]; while(cal(i) != pos) { i = cal(i); ma = (ma * 10 + a[i]); } // dbg(ma); printf("%d ",dp[ma] - 1); } return 0; }
F：
依旧是bfs搜索，vis[i][j][k][m] - 表示当空白位置为i,j，指定棋子为k,m时是否被搜到过。
然后bfs的时候我们取移动空白的位置即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 5e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int n,m,q,ex,ey,sx,sy,tx,ty,b[4][2] = {1,0,-1,0,0,1,0,-1},a[35][35]; bool vis[35][35][35][35]; struct Node{ int x1,y1,x2,y2,dis; }; int solve() { memset(vis,0,sizeof(vis)); queue<Node> Q; Q.push(Node{ex,ey,sx,sy,0}); vis[ex][ey][sx][sy] = 1; while(!Q.empty()) { Node q = Q.front(); Q.pop(); if(q.x2 == tx && q.y2 == ty) return q.dis; for(int i = 0;i < 4;++i) { int px = q.x1 + b[i][0]; int py = q.y1 + b[i][1]; if(px >= 1 && px <= n && py >= 1 && py <= m && a[px][py] != 0) { if(px == q.x2 && py == q.y2) { if(!vis[q.x2][q.y2][q.x1][q.y1]) { //printf("(%d,%d) (%d,%d) to (%d,%d) (%d,%d) pos1 ",q.x1,q.y1,q.x2,q.y2,q.x2,q.y2,q.x1,q.y1); vis[q.x2][q.y2][q.x1][q.y1] = 1; Q.push(Node{q.x2,q.y2,q.x1,q.y1,q.dis + 1}); } } else if(!vis[px][py][q.x2][q.y2]){ //printf("(%d,%d) (%d,%d) to (%d,%d) (%d,%d) pos2 ",q.x1,q.y1,q.x2,q.y2,px,py,q.x2,q.y2); vis[px][py][q.x2][q.y2] = 1; Q.push(Node{px,py,q.x2,q.y2,q.dis + 1}); } } } } return -1; } int main() { n = read(),m = read(),q = read(); for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) a[i][j] = read(); while(q--) { ex = read(),ey = read(),sx = read(),sy = read(),tx = read(),ty = read(); printf("%d ",solve()); } return 0; } /* 3 4 1 0 1 1 1 0 1 1 0 0 1 0 0 1 2 1 4 3 2 */
G：
我们把一个空洞看成一个点，能到达的空洞之间建边，然后再从最下面开始bfs即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 5e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; LL x[1005],y[1005],z[1005]; int dis[1005][1005]; int n,h,r; bool vis[1005]; LL cal(int i,int j) { return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j]); } bool bfs() { queue<int> Q; for(int i = 1;i <= n;++i) { if(z[i] <= r) { Q.push(i); vis[i] = 1; } } while(!Q.empty()) { int u = Q.front(); // printf("%d ",u); Q.pop(); if(z[u] + r >= h) return true; for(int i = 1;i <= n;++i) { if(!vis[i] && dis[u][i] == 1) { vis[i] = 1; Q.push(i); } } } return false; } int main() { int ca;ca = read(); while(ca--) { memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); n = read(),h = read(),r = read(); for(int i = 1;i <= n;++i) x[i] = read(),y[i] = read(),z[i] = read(); for(int i = 1;i <= n;++i) { for(int j = 1;j <= n;++j) { if(i == j) continue; LL ma = cal(i,j); if(cal(i,j) <= 4LL * r * r) { dis[i][j] = dis[j][i] = 1; } } } printf("%s ",bfs() ? "Yes" : "No"); } return 0; }
H：
首先，我们需要知道，一个第一行的点能到达的最后一行的所有点一定是连起来的，不然中间的点别的点都无法到达。
那么我们就可以处理出每个点能到达的一条连续的区域，我们可以看成一条线段。那么最后就是一个区间覆盖的问题。
我们对所有线段左端点升序，然后贪心去找最远的右端点覆盖即可。
dfs处理每个点能到达的最左的点和最右的点。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 5e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read(){ int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int n,m,a[505][505],vis[505][505],le[505][505],ri[505][505],b[4][2] = {1,0,-1,0,0,1,0,-1}; struct Node{ int L,r; bool operator < (const Node a) const { if(L == a.L) return r > a.r; else return L < a.L; } }p[505]; void dfs(int x,int y) { if(vis[x][y]) return ; vis[x][y] = 1; if(x == n) { le[x][y] = ri[x][y] = y; } for(int i = 0;i < 4;++i) { int px = x + b[i][0]; int py = y + b[i][1]; if(px >= 1 && px <= n && py >= 1 && py <= m && a[px][py] < a[x][y]) { if(!vis[px][py]) { dfs(px,py); } le[x][y] = min(le[px][py],le[x][y]); ri[x][y] = max(ri[px][py],ri[x][y]); } } } int main() { while(~scanf("%d %d",&n,&m)) { for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) { a[i][j] = read(); vis[i][j] = ri[i][j] = 0; le[i][j] = 1000000000; } for(int i = 1;i <= m;++i) { if(vis[1][i]) continue; dfs(1,i); } int cnt = 0; for(int i = 1;i <= m;++i) { if(vis[n][i] == 0) cnt++; } if(cnt == 0) { for(int i = 1;i <= m;++i) p[i].L = le[1][i],p[i].r = ri[1][i]; sort(p + 1,p + m + 1); /* for(int i = 1;i <= m;++i) { printf("p[%d].L is %d p[%d].r is %d ",i,p[i].L,i,p[i].r); }*/ int st = 2,ans = 1,ri = p[1].r; while(ri < m && st <= m) { int mx = 0; while(p[st].L <= ri + 1 && st <= m) { mx = max(mx,p[st++].r); } ri = max(ri,mx); ans++; } printf("1 %d ",ans); } else { printf("0 %d ",cnt); } } return 0; }