A. 乳草入侵

题目大意

有一片 n*m 大小的草地，" . " 表示草，" * " 表示石头，其中点（mx,my）处有一颗乳草，乳草每个星期能往他周围八个方向生长，石头上无法长草，问至少需要多少个星期乳草就能覆盖整个草地（数据保证一定能长满整个草地）。

• 1 <= n, m <= 100
• 时限 1s

解题思路

因为问的是至少多少个星期，所以我们考虑用 bfs ，此题为模板题，直接从起点开始 bfs ，因为数据保证了一定能覆盖完是草地的格子，所以 bfs 中最后出队的格子用的时间是最长的，直接记录最后一个出队的点的星期数就是答案，注意起点为第 0 周。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int x,y,step;
};

char ch;
int n, m, mx, my, ans = 0;
int mp[105][105], vis[105][105];
int dx[10]={-1,-1,-1,0,0,1,1,1};
int dy[10]={-1,0,1,-1,1,-1,0,1};

queue<node> Q;

void bfs(int x, int y)
{
    Q.push({x,y,0});
    vis[x][y] = 1;
    while(!Q.empty()) {
        node f = Q.front();
        Q.pop();
        ans = f.step;
        for(int i = 0; i < 8; i++) {
            int nx = f.x + dx[i];
            int ny = f.y + dy[i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == 0 && vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                Q.push({nx, ny, f.step+1});
            }
        }
    }
}

int main()
{
    cin >> n >> m >> mx >> my;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> ch;
            if(ch == '.') mp[i][j] = 0;
            else if(ch == '*') mp[i][j] = 1;
        }
    }
    bfs(mx, my);
    cout << ans << endl;
    return 0;
}

B. 分糖果

题目大意

有 n 个小朋友，p 个朋友关系，现在需要发糖果，每个拿到糖果的小朋友会把多出来的部分分给还没得到糖果的朋友，但在分发的过程中，拿到糖果的小朋友会忍不住吃掉糖果，已知两个人之间需要 1 秒传递糖果，吃掉糖果需要 m 秒，问第几秒钟所有的小朋友都吃完了糖果。

• n <= 1000
• p <= 50000
• 时限 1s

解题思路

朋友关系可以组成一条边，此题本质上就是从 c 号小朋友开始，按照朋友关系进行 bfs ，因为最后一个小朋友拿到糖的时间最晚，所以总时间为最后一个小朋友拿到糖果的时间 t 加上吃糖的时间 m 。此题没有直接给出图，而是给出了两点间的关系，所以可以考虑使用邻接表建无向图。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

struct node
{
    int num;
    int step;
};
int n, p, c, m, ans = 0;
vector<int> E[maxn];
bool vis[maxn];
queue<node> qe;

void bfs(int id)
{
    qe.push({c,1});
    vis[c] = 1;
    while(!qe.empty()) {
        node f = qe.front();
        qe.pop();
        ans = max(ans, f.step);
        for(int i = 0; i < E[f.num].size(); i++) {
            int nxt = E[f.num][i];
            if(!vis[nxt]) {
                vis[nxt] = 1;
                qe.push({nxt, f.step+1});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &p, &c);
    scanf("%d", &m);
    for(int i = 1; i <= p; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        E[a].push_back(b);
        E[b].push_back(a);
    }
    bfs(c);
    printf("%d", ans+m);
    return 0;
}

C. 武士风度的牛

题目大意

有一头牛，走日字（与象棋的马的走法一样），从一个 n*m 地图的 K 出发，问最少需要多少步就能走到 H ，地图中 " . " 表示路， " * " 表示障碍。

• n , m <= 150
• 时限 1s

解题思路

bfs 模板题，注意输入的行和列是反过来的，如果没注意的话建图会出错。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;

struct node
{
    int x, y, step;
};

int m, n, sx, sy, mx, my, ans = 0;
int mp[maxn][maxn], vis[maxn][maxn];
int dis[8][4] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
queue<node> Q;

void bfs(int x, int y)
{
    Q.push({x, y, 0});
    vis[x][y] = 1;
    while(!Q.empty()) {
        node f = Q.front();
        Q.pop();
        if(f.x == mx && f.y == my) {
            ans = f.step;
            break;
        }
        for(int i = 0; i < 8; i++) {
            int nx = f.x + dis[i][0];
            int ny = f.y + dis[i][5];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == 0 && !vis[nx][ny]) {
                vis[nx][ny] = 1;
                Q.push({nx, ny, f.step+1});
            }
        }
    }
}

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            if(ch == '*') mp[i][j] = 1;
            else mp[i][j] = 0;
            if(ch == 'K') sx = i, sy = j;
            if(ch == 'H') mx = i, my = j;
        }
    }
    bfs(sx, sy);
    cout << ans;
    return 0;
}

D. 拯救王妃

题目大意

有一个 m*n 的矩阵，王妃被关在（a, b），王子要从（1, 1）出发，在 t 秒时限内救出王妃，王子可以往上下左右四个方向移动，矩阵每一个格子都有绑匪，消灭绑匪需要的时间都记录在矩阵中。如果王子能救出王妃，则输出 YES 和最大剩余时间，如果不能就输出 NO 。

• 1 <= m, n <= 70
• 题目保证答案和其他数据都在 long int 范围内
• 时限 1s

解题思路

题目问的是最大剩余时间，所以考虑 bfs ，因为消灭绑匪的时间各有不同，所以不一定最快搜到终点就一定剩余最少时间。本题的要点在于同一个点可以重复入队（即如果能靠另一条路缩小到这个点的时间，则更新该点的最短时间），我们可以用一个 tim 数组来记录到达点 (i, j) 的时间，如果新的时间 t < tim[ i ][ j ] 则说明该点可以继续入队。因为本题只有尝试过所有的方案才能的到最优解，所以直接 bfs 整幅图就可以，不用设置终点。（本来按题目要求应该开 long long，但可能数据太水，用 int 直接莽过去了）

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 75;

struct node
{
    int x,y,t;
};
int m, n, a, b, t;
int mp[maxn][maxn], tim[maxn][maxn];
int dx[5] = {-1, 1, 0, 0};
int dy[5] = {0, 0, -1, 1};
queue<node> Q;
void bfs(int x, int y)
{
    Q.push({x, y, mp[x][y]});
    tim[x][y] = mp[x][y];
    while(!Q.empty()) {
        node f = Q.front();
        Q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = f.x + dx[i];
            int ny = f.y + dy[i];
            int t = f.t + mp[nx][ny];
            if(nx >= 1 && nx <= m && ny >= 1 && ny <= n && t < tim[nx][ny]) {
                tim[nx][ny] = t;
                Q.push({nx, ny, t});
            }
        }
    }
}
int main()
{
    memset(tim, 0x3f, sizeof(tim));
    cin >> m >> n;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> mp[i][j];
        }
    }
    cin >> a >> b >> t;
    bfs(1,1);
    if(t-tim[a][b] < 0) cout << "NO";
    else cout << "YES\n" << t-tim[a][b];
    return 0;
}

E. 八数码

题目大意

有一个 3 x 3 的矩阵，有 0~8 ，其中 0 可以跟他上下左右 4 个数字进行交换，现在给你一个状态和最终状态，问最少需要多少步就可以完成转换。

• 时限 3s

解题思路

问的是最少需要多少步，考虑用 bfs ，我们可以发现，把这个矩阵拉成 1 维后，它的每一种变化都对应着一种排列，而 9 个数一共有 9! = 362880 种排列，所以 bfs 不会超时。因为需要标记排列是否出现过，所以可以考虑使用康托展开把排列转换成一个整数表示它的状态。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 11;

struct node
{
    int a[5][9];
    int x, y, step;
};

ll fact[maxn] = {1,1,2,6,24,120,720,5040,40320,362880,3628800}; // 存储1-10阶乘
int P[maxn]; // 二维转一维
int ans = 0, vis[1000005];
int dx[5] = {-1, 1, 0, 0};
int dy[5] = {0, 0, -1, 1};
ll fin;
node start, aim;
queue<node> Q;
 
ll cantor(node x, int n = 9)
{
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            P[(i-1)*3+j] = x.a[i][j];
        }
    }
    ll ans = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = i+1; j <= n; j++) {
            if(P[i] > P[j]) ans += fact[n-i]; // 统计第i位后面有多少比它小的
        }
    }
    return ans;
}

// void print(node x)
// {
    // for(int i = 1; i <= 3; i++) {
        // for(int j = 1; j <= 3; j++) {
            // cout << x.a[i][j]<<" ";
        // }
        // cout << endl;
    // }
    // cout<<endl;
// }

void bfs()
{
    Q.push(start);
    vis[cantor(start)] = 1;
    while(!Q.empty()) {
        node f = Q.front(), nxt;
        Q.pop();
        if(cantor(f) == fin) {
            ans = f.step;
            break;
        }
        for(int i = 0; i < 4; i++) {
            int nx = f.x + dx[i];
            int ny = f.y + dy[i];
            if(nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3) {
                nxt = f;
                swap(nxt.a[f.x][f.y], nxt.a[nx][ny]);
                nxt.x = nx, nxt.y = ny, nxt.step = f.step + 1;
                if(!vis[cantor(nxt)]) {
                    vis[cantor(nxt)] = 1;
                    Q.push(nxt);
                }
            }
        }
    }
}

int main()
{
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            cin >> start.a[i][j];
            if(start.a[i][j] == 0) start.x = i, start.y = j;
        }
    }
    start.step = 0;
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            cin >> aim.a[i][j];
        }
    }
    fin = cantor(aim); // 结束状态
    bfs();
    cout << ans;
    return 0;
}

版权属于：PCsky

本文链接：http://www.hyouka.club/index.php/archives/179/

转载时须注明出处及本声明