头像

WangJY

$\href{https://www.acwing.com/blog/content/19690/}{\color{black}{个人主页}}$




离线:9小时前


最近来访(689)
用户头像
毒瘤
用户头像
塔的魔法师
用户头像
许七安
用户头像
省赛加油
用户头像
whale77
用户头像
獨孤求敗
用户头像
曙光女神
用户头像
寻_0
用户头像
su尔
用户头像
寒暄a
用户头像
生在逢时
用户头像
冷无情
用户头像
Jerome
用户头像
大雪莱
用户头像
既生缘何生孽
用户头像
省选加油
用户头像
蓝冰飘零
用户头像
努力学习鸭
用户头像
冰中月
用户头像
cht


WangJY
2天前

题目描述

农民 John 有很多牛,他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力,在农场里像 Knight 一样地跳(就是我们熟悉的象棋中马的走法)。

虽然这头神奇的牛不能跳到树上和石头上,但是它可以在牧场上随意跳,我们把牧场用一个 $x,y$ 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草,给你一张地图,上面标注了 The Knight 的开始位置,树、灌木、石头以及其它障碍的位置,除此之外还有一捆草。

现在你的任务是,确定 The Knight 要想吃到草,至少需要跳多少次。

The Knight 的位置用 K 来标记,障碍的位置用 * 来标记,草的位置用 H 来标记。

这里有一个地图的例子:

         11 | . . . . . . . . . .
         10 | . . . . * . . . . . 
          9 | . . . . . . . . . . 
          8 | . . . * . * . . . . 
          7 | . . . . . . . * . . 
          6 | . . * . . * . . . H 
          5 | * . . . . . . . . . 
          4 | . . . * . . . * . . 
          3 | . K . . . . . . . . 
          2 | . . . * . . . . . * 
          1 | . . * . . . . * . . 
          0 ----------------------
                                1 
            0 1 2 3 4 5 6 7 8 9 0

The Knight 可以按照下图中的 $A,B,C,D…$ 这条路径用 $5$ 次跳到草的地方(有可能其它路线的长度也是 $5$):

         11 | . . . . . . . . . .
         10 | . . . . * . . . . .
          9 | . . . . . . . . . .
          8 | . . . * . * . . . .
          7 | . . . . . . . * . .
          6 | . . * . . * . . . F<
          5 | * . B . . . . . . .
          4 | . . . * C . . * E .
          3 | .>A . . . . D . . .
          2 | . . . * . . . . . *
          1 | . . * . . . . * . .
          0 ----------------------
                                1
            0 1 2 3 4 5 6 7 8 9 0

注意: 数据保证一定有解。

输入格式

第 $1$ 行: 两个数,表示农场的列数 $C$ 和行数 $R$。

第 $2..R+1$ 行: 每行一个由 $C$ 个字符组成的字符串,共同描绘出牧场地图。

输出格式

一个整数,表示跳跃的最小次数。

数据范围

$1≤R,C≤150$

输入样例:

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

输出样例:

5

题目分析

看到题目里面的 “最小次数” 这个词,你应该首先想到的就是 bfs (当然直接看算法标签也行)
bfs 要考虑的四点是:

  • 状态描述
  • 起始状态
  • 终止状态
  • 状态间的转移

状态描述

这道题里的状态就是一个二维坐标和起点到它走了多少步。二维坐标可以用pair<int, int>实现,起点到它走了多少步可以用dist数组记录。

起始状态

这道题里的起始状态就是地图上标注着K的地方,它到自己的距离当然是0。找到标注着K的地方的坐标可以用两层for循环,也可以用STL里面的find一行一行找。

终止状态

这道题里的终止状态就是地图上标注着H的地方,如果搜到了就返回起点到它走了多少步。

状态间的转移

这道题里的状态间的转移就是国际象棋中马的走法,如下图(马标作K,马能到的地方标作*,剩余地方标作.):(注意:国际象棋没有 “蹩马腿” 一说!不要和中国象棋搞混了!)

.*.*.
*...*
..K..
*...*
.*.*.

坐标的变化量可以用dxdy数组记录。

代码(带注释)

#include <iostream>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 160; // 开大10保险一点
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; // 坐标变化量

int n, m; // 地图的长和宽
char g[N][N]; // 地图
PII q[N * N]; // bfs要用的队列(我习惯用手写队列,但是也可以用STL里面的queue)
int dist[N][N]; // dist数组记录距离
bool st[N][N]; // st数组记录是否被搜过(也可以像y总那样不用st,把dist全初始化成-1,然后判断dist[x][y]是不是-1)

int bfs()
{
    int hh = 0, tt = 0; // 队头和队尾(队尾是0是因为要添加起点)

    int a, b; // 'K'所在的坐标
    for (int i = 0; i < n; i ++ ) // 搜!
        for (int j = 0; j < m; j ++ ) // 注意是m
            if (g[i][j] == 'K')
                a = i, b = j;

    q[0] = {a, b}; // 起点坐标入队
    dist[a][b] = 0; // 起点到自己的距离是0
    st[a][b] = true; // 标记一下起点搜过了

    while (hh <= tt) // 当队列不为空
    {
        PII t = q[hh ++ ]; // 弹出队头
        if (g[t.x][t.y] == 'H') return dist[t.x][t.y]; // 如果搜到终点了则返回

        for (int i = 0; i < 8; i ++ ) // 遍历所有的方向
        {
            int a = t.x + dx[i], b = t.y + dy[i]; // 计算坐标
            if (a < 0 || a >= n || b < 0 || b >= m) continue; // 如果跳出来地图则跳过
            if (st[a][b]) continue; // 如果搜过了也跳过
            if (g[a][b] == '*') continue; // 不能跳到障碍上

            q[ ++ tt] = {a, b}; // 入队
            dist[a][b] = dist[t.x][t.y] + 1; // 起点到新的点的距离是起点到原来的点t的距离 + 1
            st[a][b] = true; // 这个点也被搜过了
        }
    }

    return -1; // 因为数据保证有解所以不会被执行到,但是加上了会方便调试
}

int main()
{
    cin >> m >> n; // 这里有个坑点:是先输入列数再输入行数
    for (int i = 0; i < n; i ++ ) cin >> g[i]; // 读取地图的每一行

    cout << bfs(); // 输出结果

    return 0;
}

代码(不带注释)我知道你们最喜欢这个

#include <iostream>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 160;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m;
char g[N][N];
PII q[N * N];
int dist[N][N];
bool st[N][N];

int bfs()
{
    int hh = 0, tt = 0;

    int a, b;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'K')
                a = i, b = j;

    q[0] = {a, b};
    dist[a][b] = 0;
    st[a][b] = true;

    while (hh <= tt)
    {
        PII t = q[hh ++ ];
        if (g[t.x][t.y] == 'H') return dist[t.x][t.y];

        for (int i = 0; i < 8; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[a][b] == '*') continue;

            q[ ++ tt] = {a, b};
            dist[a][b] = dist[t.x][t.y] + 1;
            st[a][b] = true;
        }
    }

    return -1;
}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    cout << bfs();

    return 0;
}

代码(STL版)

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 160;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m;
char g[N][N];
queue<PII> q;
int dist[N][N];
bool st[N][N];

int bfs()
{
    int a, b;
    for (int i = 0; i < n; i ++ )
    {
        int j = find(g[i], g[i] + m, 'K') - g[i];
        if (j != m)
        {
            a = i, b = j;
            break;
        }
    }

    q.push({a, b});
    dist[a][b] = 0;
    st[a][b] = true;

    while (!q.empty())
    {
        PII t = q.front(); q.pop();
        if (g[t.x][t.y] == 'H') return dist[t.x][t.y];

        for (int i = 0; i < 8; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[a][b] == '*') continue;

            q.push({a, b});
            dist[a][b] = dist[t.x][t.y] + 1;
            st[a][b] = true;
        }
    }

    return -1;
}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    cout << bfs();

    return 0;
}


新鲜事 原文

WangJY
2天前
图片



WangJY
3天前
#include <cstring>
#include <vector>
#include <functional>

using namespace std;

template<class Type, const unsigned maxsize>
class stack
{
    private:
        Type s[maxsize];
        unsigned len;
    public:
        void push(Type t)
        {
            if (len == maxsize) return;
            s[len ++ ] = t;
        }

        Type top()
        {
            return s[len - 1];
        }

        void clear()
        {
            len = 0;
        }

        bool empty()
        {
            return len;
        }

        void pop()
        {
            if (empty()) return;
            len -- ;
        }

        unsigned size()
        {
            return len;
        }

        stack()
        {
            len = 0;
        }

        stack(Type *a, unsigned l)
        {
            len = l;
            memcpy(s, a, l * sizeof(Type));
        }

        stack(vector<Type> a)
        {
            len = a.size();
            for (unsigned i = 0; i < len; i ++ ) s[i] = a[i];
        }

        stack(vector<Type> a, unsigned l, unsigned r)
        {
            len = r - l;
            for (unsigned i = 0; i < len; i ++ ) s[i] = a[i + l];
        }

        stack(stack a)
        {
            memcpy(s, a.s, a.len);
            len = a.len;
        }
};

template<class Type, const unsigned maxsize, bool cmp(Type, Type) = greater<Type>()>
class heap
{
    private:
        Type h[maxsize];
        unsigned len = 0;
    public:
        void push(Type t)
        {
            if (len == maxsize) return;
            unsigned i;
            h[i = len ++ ] = t;
            while (i)
            {
                int f = i - 1 >> 1;
                if (cmp(h[i], h[f])) break;
                swap(h[i], h[f]);
                i = f;
            }
        }

        Type top()
        {
            return h[0];
        }

        unsigned size()
        {
            return len;
        }

        bool empty()
        {
            return len;
        }

        void pop()
        {
            if (empty()) return;
            Type t = h[0];
            h[0] = h[ -- len];
            unsigned i = 0;
            while (i << 1 < len - 1)
            {
                if (i << 1 < len - 2 && h[(i << 1) + 1] < h[i + 1 << 1])
                {
                    swap(h[i], h[i + 1 << 1]);
                    i = i + 1 << 1;
                }
                else
                {
                    swap(h[i], h[(i << 1) + 1]);
                    i = (i << 1) + 1;
                }
            }
        }

        void clear()
        {
            len = 0;
        }

        heap()
        {

        }

        heap(Type *a, int l)
        {
            for (unsigned i = 0; i < l; i ++ ) push(a[i]);
        }

        heap(vector<Type> a)
        {
            for (Type t : a) push(t);
        }

        heap(vector<Type> a, unsigned l, unsigned r)
        {
            for (unsigned i = l; i < r; i ++ ) push(a[i]);
        }

        heap(heap a)
        {
            memcpy(h, a.h, a.len);
            len = a.len;
        }
};

template<class Type, const unsigned maxsize, bool cmp(Type, Type) = less<Type>()>
class min_stack
{
    private:
        Type s[maxsize], m[maxsize];
        unsigned len = 0;
    public:
        void push(Type t)
        {
            if (len == maxsize) return;
            s[len] = t;
            if (!len) m[len] = t;
            else m[len] = (m[len - 1] ? cmp(m[len - 1], t) : t);
            len ++ ;
        }

        Type top()
        {
            return s[len - 1];
        }

        unsigned size()
        {
            return len;
        }

        bool empty()
        {
            return len;
        }

        void clear()
        {
            return len;
        }

        void pop()
        {
            if (!len) return;
            len -- ;
        }

        Type min()
        {
            return m[len - 1];
        }

        min_stack()
        {

        }

        min_stack(Type *a, unsigned l)
        {
            for (unsigned i = 0; i < l; i ++ ) push(a[i]);
        }

        min_stack(vector<Type> a)
        {
            for (Type t : a) push(t);
        }

        min_stack(vector<Type> a, unsigned l, unsigned r)
        {
            for (unsigned i = l; i < r; i ++ ) push(a[i]);
        }

        min_stack(min_stack a)
        {
            memcpy(s, a.s, a.len);
            memcpy(m, a.m, a.len);
            len = a.len;
        }
};


新鲜事 原文

WangJY
4天前
第二次AK!!!
图片


新鲜事 原文

WangJY
4天前
图片



WangJY
5天前
#include <iostream>

using namespace std;

const int N = 100010;

int n, m, res;
string op[N];
int t[N];

bool calc(bool x, int i)
{
    for (int j = 0; j < n; j ++ )
    {
        bool d = t[j] >> i & 1;
        if (op[j] == "OR") x |= d;
        else if (op[j] == "XOR") x ^= d;
        else x &= d;
    }

    return x;
}

int main()
{
    ios::sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> op[i] >> t[i];

    int s = 0;
    for (int i = 29; ~i; i -- )
        if (s + (1 << i) <= m && calc(1, i) > calc(0, i)) s += 1 << i, res |= 1 << i;
        else res |= calc(0, i) << i;

    cout << res;

    return 0;
}


活动打卡代码 AcWing 448. 表达式的值

WangJY
6天前
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

typedef pair<int, int> PII;
#define f first
#define s second

const int MOD = 10007;

stack<char> op;
stack<PII> num;

void eval()
{
    PII b = num.top(); num.pop(); // a和b交换也可以,因为交换不会影响结果
    PII a = num.top(); num.pop();
    char c = op.top(); op.pop();

    if (c == '+') num.push({a.f * b.f % MOD, (a.f * b.s + a.s * b.f + a.s * b.s) % MOD});
    else if (c == '*') num.push({(a.f * b.f + a.f * b.s + a.s * b.f) % MOD, a.s * b.s % MOD}); // 可以用else,但是……用else if是好习惯嘛
}

int main()
{
    int l;
    string expr;
    cin >> l >> expr;

    num.push({1, 1});

    for (int i = 0; i < l; i ++ )
        if (expr[i] == '(') op.push('(');
        else if (expr[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (!op.empty() && op.top() != '(' && expr[i] >= op.top()) eval();
            op.push(expr[i]);
            num.push({1, 1});
        }

    while (!op.empty()) eval();

    cout << num.top().f;

    return 0;
}


活动打卡代码 AcWing 1442. 单词处理器

WangJY
6天前
#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    int cnt = 0;
    while (n -- )
    {
        string word;
        cin >> word;
        if (cnt + word.size() <= m)
        {
            if (cnt) cout << ' ';
            cout << word;
            cnt += word.size();
            continue;
        }
        cout << '\n' << word;
        cnt = word.size();
    }

    return 0;
}


活动打卡代码 AcWing 442. 接水问题

WangJY
8天前
#include <iostream>

using namespace std;

const int N = 10010, M = 110;

int n;
int a[N], w[M];

int main()
{
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) w[i] = a[i];

    int next = m, res = 0;
    while (next < n)
    {
        bool flag = false;
        for (int i = 0; i < m; i ++ )
        {
            w[i] -- ;
            if (!w[i] && !flag) w[i] = a[next ++ ];
            if (next >= n) flag = true;
        }

        res ++ ;
        if (flag) break;
    }

    int maxv = 0;
    for (int i = 0; i < m; i ++ ) maxv = max(maxv, w[i]);

    cout << res + maxv;

    return 0;
}


活动打卡代码 AcWing 450. 寻宝

WangJY
9天前
#include <iostream>

using namespace std;

const int N = 10010, M = 110, mod = 20123;

int n, m;
bool st[N][M];
int x[N][M];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> st[i][j] >> x[i][j];

    int r;
    cin >> r;

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res = (res + x[i][r]) % mod;

        int cnt = 0;
        for (int j = 0; j < m; j ++ ) cnt += st[i][j];
        for (int j = 0; j < m; j ++ ) x[i][j] %= cnt;

        int t = x[i][r];
        if (!t) t = cnt;

        for (int j = r; ; j = (j + 1) % m)
            if (st[i][j] && ! -- t)
            {
                r = j;
                break;
            }
    }

    cout << res;

    return 0;
}