HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 05-13

2021-05-13 20:59:23 By 张义丰

05-13——搜索 P2----------------

OJ-81 小明回家

flag 0-没手机 1-有手机


0 有手机、没手机,都没来过

1 没手机,来过

2 有手机,来过

3 有手机、没手机,都来过

重点:按位保存状态

```c++
/*************************************************************************
    > File Name: 81.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 13 May 2021 06:26:59 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node {
    int x, y, step, flag;
};
int n, m, sx, sy, mark[2005][2005];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[2005][2005];
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            cin >> mmap[i][j];
            if (mmap[i][j] == 'S') {
                sx = i, sy = j;
            }
        }
    }
    queue<node> que;
    que.push((node){sx, sy, 0, 0});
    mark[sx][sy] = 1;
    while  (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i) {
            int x = temp.x +dir[i][0];
            int y = temp.y +dir[i][1];
            if (temp.flag == 0 && (mark[x][y] & 1) != 0) {
                continue;
            }
            if (temp.flag == 1 && (mark[x][y] & 2) != 0) {
                continue;
            }
            if (temp.flag == 1 && mmap[x][y] == 'T') {
                cout << temp.step + 1 << endl;
                return 0;
            }
            if (mmap[x][y] == 'S' || mmap[x][y] == 'T' || mmap[x][y] == '.') {
                mark[x][y] += temp.flag + 1;
                que.push((node){x, y, temp.step + 1, temp.flag});
            }
            if (mmap[x][y] == 'P'){
                mark[x][y] = 3;
                que.push((node){x, y, temp.step + 1, 1});

            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

原来写的c语言的代码,思路:分别从起点和终点出发跑两遍BFS

#include <stdio.h>
#include <string.h>
#define MAXN 2003
#define INF 1000000000
int n, m, head, tail, end_x, end_y, start_x, start_y, ans = INF;
int dx[4] = {1, 0, -1 ,0};
int dy[4] = {0, 1, 0, -1};
struct pos{
    int x, y, step;
}tmp, q[MAXN * MAXN];
char a[MAXN][MAXN];
int vis[MAXN][MAXN];
int vis2[MAXN][MAXN];
int main(){
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; ++i){
        scanf("%s", a[i]+1);
    }

    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            if (a[i][j] == 'S'){
                start_x = i, start_y = j;
            } else if (a[i][j] == 'T'){
                end_x = i, end_y = j;
            }
        }
    }
    memset(vis, -1, sizeof(vis));
    memset(vis2, -1, sizeof(vis2));
    head = 0, tail = 0;
    q[tail].x = start_x, q[tail].y = start_y, q[tail].step = 0;
    tail ++;
    vis[start_x][start_y] = INF;
    while (head < tail){
        int now_x = q[head].x, now_y = q[head].y, s = q[head].step;
        for (int i=0; i<4; ++i){
            int new_x = now_x + dx[i], new_y = now_y + dy[i];
            if (new_x > 0 && new_x <= n && new_y > 0 && new_y <= m && a[new_x][new_y] != '#' && vis[new_x][new_y] == -1){
                q[tail].x = new_x, q[tail].y = new_y, q[tail].step = s+1;
                vis[new_x][new_y] = INF;
                if (a[new_x][new_y] == 'P'){
                    vis[new_x][new_y] = s+1;
                }
                tail ++;
            }
        }
        head ++;
    }
    head = 0, tail = 0;
    q[tail].x = end_x, q[tail].y = end_y, q[tail].step = 0;
    tail ++;
    vis2[end_x][end_y] = INF;
    while (head < tail){
        int now_x = q[head].x, now_y = q[head].y, s=q[head].step;
        for (int i=0; i<4; ++i){
            int new_x = now_x +dx[i], new_y = now_y +dy[i];
            if (new_x > 0 && new_x <=n && new_y >0 && new_y <=m && a[new_x][new_y] != '#' && vis2[new_x][new_y] == -1){
                q[tail].x = new_x, q[tail].y = new_y, q[tail].step = s+1;
                vis2[new_x][new_y] = INF;
                if (ans > vis[new_x][new_y]+s+1){
                    ans = vis[new_x][new_y]+s+1;
                }
                tail ++;
            }
        }
        head ++;
    }
    printf("%d\n", ans);
    return 0;
}

船长说如果有多种商店,这个方法就行不通了。

我觉得也是可以的

OJ-527 飞跃原野

注意:对于不同能量分别去重

/*************************************************************************
    > File Name: 527.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 13 May 2021 06:52:46 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, y, step, d;
};
int n, m, d;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
char mmap[105][105], mark[105][105][105];
int main(){
    cin >> n >> m >> d;
    for (int i =1 ; i<= n; ++i) {
        cin >> &mmap[i][1];
    }
    queue<node> que;
    que.push((node){1, 1, 0, d});
    for (int i = 0; i<=d; ++i) {
        mark[1][1][i] = 1;
    }
    while (!que.empty()){
        node temp = que.front();
        que.pop();
        for (int i=0; i<4; ++i){
            for (int j=2; j <= temp.d; ++j){
                int x = temp.x + dir[i][0] * j;
                int y = temp.y + dir[i][1] * j;
                if (mmap[x][y] == 0) {
                    break;
                }
                if (x == n && y == m) {
                    cout << temp.step + 1 << endl;
                    return 0;
                }
                if (mmap[x][y] == 'P' && mark[x][y][temp.d - j] == 0){
                    mark[x][y][temp.d - j] = 1;
                    que.push((node){x, y, temp.step + 1, temp.d - j});
                }
            }
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (x == n && y == m){
                cout << temp.step + 1 << endl;
                return 0;
            }
            if (mmap[x][y] == 'P' && mark[x][y][temp.d] == 0) {
                mark[x][y][temp.d] = 1;
                que.push((node){x, y, temp.step + 1, temp.d});
            }
        }
    }
    cout << "impossible" << endl;
    return 0;
}

是不是可以用贪心的策略呢?

OJ-402 奇怪的电梯

/*************************************************************************
    > File Name: 402_2.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 13 May 2021 07:26:26 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node {
    int now, step;
};
int n, a, b, num[205], mark[205];
int main(){
    cin >> n >> a >> b;
    for (int i=1; i<=n; ++i) {
        cin >> num[i];
    }
    queue<node> que;
    que.push((node){a, 0});
    mark[a] = 1;
    while (!que.empty()){
        node temp = que.front();
        que.pop();
        if (temp.now == b) {
            cout << temp.step << endl;
            return 0;
        }
        int up = temp.now + num[temp.now];
        int down = temp.now - num[temp.now];
        if (up <= n && mark[up] == 0) {
            mark[up] = 1;
            que.push((node){up, temp.step + 1});
        }
        if (down > 0 && mark[down] == 0){
            mark[down] =1 ;
            que.push((node){down, temp.step+1});
        }
    }
    cout << -1 << endl;
    return 0;
}

与之前的区别:判断队首元素是不是目标状态

优点:如果起点就是目标状态,不需要特判

缺点:把本层都搜完后才能找到目标状态

OJ-528 关系网络

/*************************************************************************
    > File Name: 528_2.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 13 May 2021 07:44:24 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    int now, step;
};
int n, x, y, arr[105][105], mark[105];
int main(){
    cin >> n >> x >> y;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=n; ++j){
            cin >> arr[i][j];
        }
    }
    queue<node> que;
    que.push((node){x, 0});
    mark[x] = 1;
    while (!que.empty()){
        node temp = que.front();
        que.pop();
        for (int i=1; i<=n; ++i){
            if (arr[temp.now][i] == 1 && mark[i] == 0){
                if (i == y){
                    cout << temp.step << endl;
                    return 0;
                }
                mark[i] = 1;
                que.push((node){i, temp.step + 1});
            }
        }
    }
    cout << 0 << endl;
    return 0;
}

这题用Floyed也AC了

/*************************************************************************
    > File Name: 528.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 13 May 2021 07:42:07 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int a[105][105], n, x, y, t;
int main(){
    memset(a, 0x3f, sizeof(a));
    cin >> n >> x >> y;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            cin >> t;
            if (i != j && t == 0) continue;
            a[i][j] = t;
        }
    }
    for (int k = 1; k<=n; ++k){
        for (int i = 1; i<=n; ++i){
            for (int j=1; j<=n; ++j){
               if (i == j) continue;
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    if (a[x][y] == 0x3f3f3f3f) cout << 0 << endl;
    else cout << a[x][y]-1 << endl;
    return 0;
}

OJ-530 警察找车(选做的作业)

OJ-529 龙与虫(选做的作业)

预处理所有出终点的位置:以敌人为出发点,8个方向

注意多组输入数据

OJ-531 奇怪的电视

二进制位存储状态

/*************************************************************************
    > File Name: 531.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 13 May 2021 08:44:14 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node {
    int status, step;
};
int n, start, num[30], b2[30], mark[10000000];
int main(){
    b2[0] = 1;
    for (int i=1; i<=20; ++i){
        b2[i] = b2[i-1]*2;
    }
    cin >> n;
    for (int i=1; i<=n; ++i){
        int t;
        cin >> t;
        if (t == 1){
            start += b2[i];
        }
    }
    for (int i=1; i<=n; ++i){
        int cnt;
        cin >> cnt;
        for (int j=0; j<cnt; ++j){
            int t;
            cin >> t;
            num[i] += b2[t];
        }
    }
    queue<node> que;
    que.push((node){start, 0});
    mark[start] = 1;
    while (!que.empty()){
        node temp = que.front();
        que.pop();
        if (temp.status == 8) {//终点
            cout << temp.step << endl;
            return 0;
        }
        for (int i=1; i<=n; ++i){
            if ((temp.status & b2[i]) == 0) {//如果没按
                int t= temp.status + b2[i];//按
                t &= ~num[i];//弹
                if (mark[t] == 0){
                    que.push((node){t, temp.step + 1});
                    mark[t] = 1;

                }
            }
        }
    }
    cout << "NO"<< endl;
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。