《搜索专题练习-题解》

2021/5/6 18:55:57

本文主要是介绍《搜索专题练习-题解》,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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\n",dp[s2[0] - '0'][s2[1] - '0'][s2[2] - '0'][s2[3] - '0']);
    }
    return 0;
}
View Code

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)\n",q.x,q.y,q.prex,q.prey,pxx,pyy);
                if(dfs(q.prex,q.prey,q.x,q.y,pxx,pyy)) {
                   // printf("YES\n");
                    vis[px][py][pxx][pyy] = 1;
                    Q.push(Node{px,py,q.dis + 1,q.x,q.y});
                }
                else {
                   // printf("no\n");
                }
            }
        }
    }
    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\n",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
*/
View Code

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\n",bfs() ? "YES" : "NO");
    }
    return 0;
}
View Code

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\n",ans);
    return 0;
}
View Code

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\n",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\n",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\n",dp[ma] - 1);
    }
    return 0;
}
View Code

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\n",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\n",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\n",solve());
    }
    return 0;
}
/*
3 4 1
0 1 1 1
0 1 1 0
0 1 0 0
1 2 1 4 3 2
*/
View Code

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\n",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\n",bfs() ? "Yes" : "No");
    }
    return 0;
}
View Code

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\n",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\n%d\n",ans);
        }
        else {
            printf("0\n%d\n",cnt);
        }
    }
    return 0;
}
View Code

 



这篇关于《搜索专题练习-题解》的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程