牛客寒假算法基础集训营6

A.出题

题目描述：

小B准备出模拟赛。
她把题目按难度分为四等，分值分别为6,7,8,9。
已知小B共出了m道题，共n分。
求小B最少出了多少道6分题。

输入描述:

两个正整数n,m

输出描述:

一个数，表示答案。
若无解，输出”jgzjgzjgz”。

输入

34 5

32 5

5 1

输出

1

3

jgzjgzjgz

备注：

$ n,m \leq 10^{12} $

思路：

简单数学！这题比赛时居然没做出来qwq，就差在草稿纸上写一下不等式……显然有解的充要条件是 $ 6m \leq n \leq 9m $。若有解：设有 $ x \; (0 \leq x \leq m) $ 道6分题，则剩下的 $ m-x $ 题共 $ n-6x $ 分，其有解的充要条件为 $ 7(m-x) \leq n-6x \leq 9(m-x) $，解得 $ 7m-n \leq x \leq \frac{9m-n}{3} $，即答案为 $ max(0, 7m-n) $。（像这类求最少的问题可以根据题目条件列出不等式找答案qwq）

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m;
int main() {
    while(cin >> n >> m){
        if(6LL * m > n || n > 9LL * m ) puts("jgzjgzjgz");
        else cout << max(0LL, 7LL * m - n) << endl;
    }
    return 0;
}

B.煤气灶

题目描述：

小j开始打工，准备赚钱买煤气灶。
第一天，小j的工资为n元，之后每天他的工资都比前一天多d元。
已知煤气灶需要m元，求小j最少工作几天才能买到煤气灶。

输入描述:

四个整数 $ n,m,d,x $ 分别表示小j第一天的工资，煤气灶的价格，工资每天的增长量，答案不超过x

输出描述:

一个数表示答案

输入

10 100 20 100

输出

4

说明

10+30+50+70>=100

备注:

$ 0 \leq n,d \leq 10^9,n+d>0 $
$ 1 \leq m \leq 10^{18} $
$ 1 \leq x \leq 10^9 $

思路：

简单的等差数列求和！因为数据太大，所以既不能暴力也不能直接用求根公式解未知数x。正解：二分答案！做这道题早就想到要二分了，但交了2发WA之后发现爆long long，于是简单地写了个python再交一发就过了。赛后看了一下题解，get新技能：用除法代替乘法避免爆long long。假设小j工作了k天，则总工资 $ = n \times k + d \times \frac{k(k-1)}{2} \ge m $，移项整理得：$ d \times k(k-1) \ge 2(m-n \times k) $。因为 $ a \times b \ge c \Leftrightarrow a \ge \left \lceil \frac{c}{b} \right \rceil $，其中 $ \left \lceil x \right \rceil $ 表示将x上取整，所以判别式分两种情况：①若 $ d = 0 $，则不等式变为 $ n \times k \ge m $；②若 $ d \neq 0 $，则不等式变为 $ k(k-1) \ge \left \lceil \frac{2(m-n \times k)}{d} \right \rceil = \frac{2(m-n \times k) +(d -1)}{d} $，以此为条件进行二分，这样就避免了不等式左边爆long long的情况。求解一元二次方程常用二分解法！

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e9;
LL n, m, d, x, lt, rt, mid, ans;
bool check(LL k) {
    if(!d) return n * k >= m;
    else return k * (k - 1LL) >= (2LL * (m - n * k) + d - 1LL) / d;
}
int main() {
    while(cin >> n >> m >> d >> x) {
        lt = 1LL, rt = inf, ans = x; //若没有进行二分判断，那么ans为给定的x
        while(lt <= rt) {
            mid = (lt + rt) >> 1;
            if(check(mid)) ans = mid, rt = mid - 1LL; //若满足条件，则找更少的天数，即右区间左移
            else lt = mid + 1LL;
        }
        cout << ans << endl;
    }
    return 0;
}

C.项链

题目描述：

小B想给她的新项链染色。
现在有m种颜色，对于第i种颜色，小B有a_i单位的颜料，每单位颜料可以染项链的一个珠子；同时，小B对于第i种颜色的喜爱度为b_i。
已知项链有n个珠子，求染色后每个珠子的颜色的喜爱度之和的最大值。
(每个珠子只能至多被染一次，不被染色则喜爱度为0)

输入描述:

第一行两个数n,m
第二行m个数 $ a_i $
第三行m个数 $ b_i $

输出描述:

一个数表示答案

输入

5 3
1 2 3
3 2 1

5 3
1 2 1
3 2 1

输出

9

8

备注：

$ 1 \leq n,m \leq 10^5, 0 \leq a_i,b_i \leq 10^6 $

思路：

按喜爱度降序排，依次贪心即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
struct node{LL a, b;} nod[maxn];
int n, m; LL ans;
bool cmp(node xx, node yy) {return xx.b > yy.b;}
int main() {
    while(cin >> n >> m){
        ans = 0LL;
        for(int i = 0; i < m; ++i) cin >> nod[i].a;
        for(int i = 0; i < m; ++i) cin >> nod[i].b;
        sort(nod, nod + m, cmp);
        for(int i = 0; i < m; ++i) {
            if(n - nod[i].a >= 0) ans += nod[i].a * nod[i].b, n -= nod[i].a;
            else {ans += nod[i].b * n; break;} //注意：剩下的珠子计算完之后直接break掉
        }
        cout << ans << endl;
    }
    return 0;
}

D.美食

题目描述：

小B喜欢美食。现在有n个美食排成一排摆在小B的面前，依次编号为 $ 1 \cdots n $，编号为i的食物大小为 $ a[i] $，即足够小B吃 $ a[i] $ 口。
小B每次会吃两口，这两口要么是编号相同的美食，要么是编号之差的绝对值为1的美食。小B想知道，她最多能吃几次？

输入描述:

第1行一个正整数n，表示美食个数
接下来n行，第i行一个整数 $ a[i] $，表示编号为i的美食的大小

输出描述:

一个数表示小B最多吃几次。

输入

4
1
5
7
8

输出

10

说明

用二元组(a,b)表示某一次吃的两个美食分别为第a个美食和第b个美食，则下面为一个吃10次的方案：$ (1,2)(2,2)(2,2)(3,4)(3,4)(3,4)(3,4)(3,4)(3,4)(3,4) $
注意不一定要吃完。

备注:

$ 1 \leq n \leq 10^5, 0 \leq a[i] \leq 10^9 $

思路：

简单贪心！模拟一下样例即可得出策略。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
LL n, a[maxn], ans;
int main() {
    while(cin >> n) {
        ans = 0LL;
        memset(a, 0, sizeof(a));
        for(LL i = 0; i < n; ++i) cin >> a[i];
        for(LL i = 0; i < n; ++i) {
            if(a[i] % 2 == 1 && a[i + 1] > 0LL) ans++, a[i + 1]--;
            ans += a[i] / 2;
        }
        cout << ans << endl;
    }
    return 0;
}

E.海啸

题目描述

有一个沿海地区，可以看作有n行m列的城市，第i行第j列的城市海拔为 $ h[i][j] $。
由于沿海，所以这个地区经常会发生海啸。海啸发生时，部分城市会被淹没，具体来说，海水高度会达到d，因此海拔低于d的城市都会被淹没。现在有q次询问，每次问你一个矩形区域中，有多少城市不会被淹没。

输入描述:

第一行三个整数n,m,d，具体含义见题目描述。
接下来n行，每行m个整数，其中第i行第j列的整数为 $ h[i][j] $，具体含义见题目描述。
第n+2行一个整数q，表示询问数。
接下来q行，每行四个整数a,b,x,y，
表示询问从第a行第b列到第x行第y列的矩形地区中，有多少地区不会被淹没。
即有多少个i,j，满足 $ a \leq i \leq x,b \leq j \leq y $，且 $ h[i][j] \ge d $ 。

输出描述:

共q行，第i行一个整数，表示第i个询问的答案。

输入

3 3 3
1 2 3
2 1 5
4 3 2
2
1 2 2 3
2 1 3 3

输出

2
3

备注:

$ 1 \leq n×m \leq 10^6 $
$ 1 \leq q \leq 10^5 $
$ 0 \leq d,h[i][j] \leq 10^9 $
$ 1 \leq a \leq x \leq n, 1 \leq b \leq y \leq m $

思路：

二维树状数组求前缀和！注意：vector容器的大小要么一开始申请好，要么push_back往容器加元素，但后者大小取决于压入元素的个数。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
vector<int> vec[maxn], num[maxn];
int n, m, d, a, b, x, y, q;
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
void add(int x, int y, int val){
    for(int i = x; i <= n; i += i & -i)
        for(int j = y; j <= m; j += j & -j)
            num[i][j] += val;
}
int query(int x, int y){
    int ans = 0;
    for(int i = x; i > 0; i -= i & -i)
        for(int j = y; j > 0; j -= j & -j)
            ans += num[i][j];
    return ans;
}
int main() {
    while(~scanf("%d%d%d", &n, &m, &d)) {
        for(int i = 0; i <= n; ++i) vec[i].clear(), num[i].clear(); //先清理
        for(int i = 0; i <= n; ++i) vec[i].resize(m + 5), num[i].resize(m + 5); //再申请二维空间
        for(int i = 1; i <= n ; ++i) {
            for(int j = 1; j <= m; ++j) {
                vec[i][j] = read();
                if(vec[i][j] >= d) add(i, j, 1);
            }
        }
        q = read();
        while(q--) {
            a = read(), b = read(), x = read(), y = read();
            printf("%d\n", query(x, y) - query(a - 1, y) - query(x, b - 1) + query(a - 1, b - 1));
        }
    }
    return 0;
}

F.石头剪刀布

题目描述：

wzms 今年举办了一场剪刀石头布大赛，bleaves 被选为负责人。
比赛共有 $ 2^n $ 个人参加，分为n轮，在每轮中，第 1 位选手和第 2 位选手对战，胜者作为新的第 1 位选手，
第 3 位和第 4 位对战，胜者作为新的第 2 位选手，以此类推。
bleaves 调查得知，每个人都有其偏爱决策，每个人在每一次对战中都会使用他的偏爱决策。如果一次对战的双方的偏爱决策相同，那么这次对战就永远不会结束，所以 bleaves 不希望这种情况发生。
现在 bleaves 知道了每个人的偏爱决策，但她不知道如何安排初始的次序，使得上面的情况不会发生，你能帮帮她吗？

输入描述:

一行三个整数 R,P,S ，表示偏爱石头，布，剪刀的人数分别为 R,P,S 。

输出描述:

如果无解，输出 IMPOSSIBLE ；
否则输出一个长度为 $ R+P+S $ 的字符串，第i个字符表示初始时第i位选手的偏爱决策，如果有多种方案，输出字典序最小的。

输入

1 1 0

2 0 0

1 1 2

输出

PR

IMPOSSIBLE

PSRS

说明

只有 2 个选手，一个偏爱石头，一个偏爱布，无论次序如何，偏爱布的选手都会胜出。
所以方案可以是 PR 和 RP ，其中字典序最小的 PR 。

备注:

全部的输入数据满足：$ R+P+S=2^n, 1 \leq n \leq 20 $。

思路：

这道题应该是整场较难的了，若能想到下面这位大佬的解法（个人觉得非常好理解），那就简单多了，很感谢某位已AK的大佬赛后提供的精彩题解，Orz！根据大佬的思路，重新整理了一下想法：根据获胜者的偏爱决策可以推出对战的两人的偏爱决策，所以这题要先从结局来反推初始状态的3个已知量是否有解。若有解，只需根据偏爱决策来递归处理字典序即可。
先规定一下：0代表石头，1代表布，2代表剪刀。
若最后一场获胜者为1（布），根据偏爱决策可得最后一局的组合为（1，0），倒数第二局的组合为（1，0）和（0，2），倒数第三局的组合为（1，0）……
从结局枚举到之前的状态可知若一轮比赛结束时的状态确定了，则这轮比赛刚开始时的状态也一定是确定的。
举个栗子：假设一轮比赛结束后，剩下x个0，y个1，z个2，那么这轮比赛开始时，一定有这样的组合：x局（0，2），y局（1，0），z局（2，1）。
设一轮比赛开始时有A个0，B个1，C个2，则有 $ A = x + y, B = y + z, C = x + z $，
解得 $ x=\frac{A+C-B}{2}, y=\frac{A+B-C}{2}, z=\frac{B+C-A}{2} $。
于是，我们就找到了递归（终止）条件：根据题目已给的A,B,C，递归求解下一场的状态，若最终能化成0,0,1的状态，则说明存在一种策略，否则不存在。
接下来就更简单了，通过前面已推得最终的获胜者，那么就可以反推出之前所有的比赛情况，所以只需先递归下来求出结果，然后每次回溯时都判断一下输出最小字典序即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int stone, cloth, scissors, winner; //石头、布，剪刀，赢家
int check(int _stone, int _cloth, int _scissors) {
    if(_stone < 0 || _cloth < 0 || _scissors < 0) return -1;
    if(_stone == 0 && _cloth == 0 && _scissors == 0) return -1;
    if(_stone == 1 && _cloth == 0 && _scissors == 0) return 0; //石头赢
    if(_stone == 0 && _cloth == 1 && _scissors == 0) return 1; //布赢
    if(_stone == 0 && _cloth == 0 && _scissors == 1) return 2; //剪刀赢
    return check((_stone + _scissors - _cloth) >> 1, (_stone + _cloth - _scissors) >> 1, (_cloth + _scissors - _stone) >> 1);
}
string get_ans(int _winner, int _stat) {
    if(_stat == 1) {
        if(_winner == 0) return "RS"; //石头赢
        else if(_winner == 1) return "PR"; //布赢
        else return "PS"; //剪刀赢
    }
    if(_winner == 0) { //石头
        string s1 = get_ans(0, _stat >> 1);
        string s2 = get_ans(2, _stat >> 1);
        if(s1 < s2) return s1 + s2; //字典序最小
        else return s2 + s1;
    }else if(_winner == 1) { //布
        string s1 = get_ans(1, _stat >> 1);
        string s2 = get_ans(0, _stat >> 1);
        if(s1 < s2) return s1 + s2;
        else return s2 + s1;
    }else { //剪刀
        string s1 = get_ans(2, _stat >> 1);
        string s2 = get_ans(1, _stat >> 1);
        if(s1 < s2) return s1 + s2;
        else return s2 + s1;
    }
}
int main() {
    while(cin >> stone >> cloth >> scissors) {
        winner = check(stone, cloth, scissors);
        if(winner == -1) {puts("IMPOSSIBLE"); continue;} //无解
        cout << get_ans(winner, (stone + cloth + scissors) >> 1) << endl;
    }
    return 0;
}

G.区间或和

题目描述：

求 $ a|(a+1)|(a+2)| \cdots |(b-1)|b $ 。
其中|表示 [按位或]。

输入描述:

多组输入，每行两个数表示a和b

输出描述:

对于每组输入，输出一个数 $ a|(a+1)|(a+2)| \cdots |(b-1)|b $。

输入

99 109
68 77
55 66
34 43
1111234 1114321

输出

111
79
127
47
1179647

备注:

输入不超过10000行，$ 0 \leq a,b \leq 10^{18}, a \leq b $

思路：

先标记区间左右端点值的二进制中1的位置，然后枚举63个二进制位，再标记一下区间左端点a加上每一位对应的十进制值是否不超过b，最后累加一下二进制中所有被标记为1的位对应的十进制数即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 65;
LL a, b, ans, bit[maxn];
int main() {
    while(cin >> a >> b) {
        memset(bit, 0, sizeof(bit)); ans = 0;
        for(LL i = 0LL; i < 63; ++i) {
            if((1LL<<i) & a) bit[i] = 1;
            if((1LL<<i) & b) bit[i] = 1;
        }
        for(LL i = 0; i < 63; ++i) {
            if((1LL<<i) + a <= b) bit[i] = 1;
            else break;
        }
        for(LL i = 0; i < 63; ++i)
            if(bit[i]) ans += 1LL<<i;
        cout << ans << endl;
    }
    return 0;
}

H.肥猪

题目描述：

小B来到了一个异世界，成为了肥猪之王。
在这个异世界，共有n种肥猪，编号分别为 $ 1,\cdots,n $。小B希望集齐这n种肥猪。
召集肥猪有两种方式：
1.花费 $ a[i] $ 的金币召唤一只编号为i的肥猪。
2.花费x的金币使所有已召集的肥猪进化。
即编号为i的肥猪编号变成i+1，特殊的，编号为n的肥猪编号变成1。请问小B最少要花多少金币才能集齐n种肥猪。

输入描述:

第一行两个正整数n,x
接下来n行，第i行一个正整数 $ a[i] $

输出描述:

一个数表示答案

输入

2 10
1
20

4 10
1
2
3
4

输出

12

10

备注：

$ 1 \leq n \leq 2000, 1 \leq x, a[i] \leq 10^9 $.

思路：

由题可知，小B最多使用n-1次进化技能。数组a表示不使用进化技能下每种猪的召集成本，数组b表示使用了j个进化技能后，每种猪对应的最小召集成本。解法：暴力枚举 $ 1 \sim n - 1 $ 次进化，求出其中（花费x或 $ a[i] $ 的金币）召集的最小代价即可！

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2005;
LL n, x, ans, tmp, a[maxn], b[maxn];
int main() {
    while(cin >> n >> x) {
        ans = 0LL;
        for(LL i = 0; i < n; ++i) cin >> a[i], ans += (b[i] = a[i]);
        for(LL j = 1; j < n; ++j) { //至多使用n-1次技能
            tmp = x * j;
            for(LL i = 0; i < n; ++i) {//n种（要进化的）肥猪
                if(b[(i + j) % n] > a[i]) tmp += (b[(i + j) % n] = a[i]); //更新b数组第i种猪第j次进化后得到的最小召集成本
                else tmp += b[(i + j) % n];
            }
            ans = min(ans, tmp);
        }
        cout << ans << endl;
    }
    return 0;
}

I.wzoi

题目描述：

bleaves 最近在 wzoi 上面做题。
wzoi 的题目有两种，一种是 noip 题，一种是省选题。
bleaves 的做题方式很特别。每一天，她可能会看一道题目，这时她会选择题目种类，然后 wzoi 会在选定种类中随机扔给她一道她还没看过的题，她会把这道题看一遍，然后存在脑子里慢慢思考；她也有可能写题，这时她一定会写没写过的题中看的时间最迟的一题(如果不存在没写过的且没看过的题，她就不能写题)。
wzoi 每天会有一个推荐的题目种类，
如果 bleaves 看一道题目：如果种类和推荐的相同，那么这道题目最大得分为10，否则为5；如果 bleaves 写一道题目：如果种类和推荐的相同，那么这道题目得分为最大得分，否则为最大得分-5；
假如 bleaves 现在还没看过任何一题，并且她知道了 wzoi 接下来一些天每天推荐的种类，问她在这些天的最大得分。

输入描述:

一行一个01串 s ，|s| 表示天数，$ s_i=0 $ 表示 wzoi 第 i 天推荐 noip 题，$ s_i=1 $ 表示 wzoi 第 i 天推荐省选题。

输出描述:

一行一个整数最大得分。

输入

0011

0101

0110

输出

20

10

20

说明：

样例一：4天行动依次为：看一道 noip 题，写第1天看的题，看一道省选题，写第3天看的题。
样例二：4天行动依次为：看一道 noip 题，写第1天看的题，看一道noip题，写第3天看的题。
样例三：4天行动依次为：看一道 noip 题，看一道省选题，写第2天看的题，写第1天看的题。

备注:

全部的输入数据满足：$ 1 \leq n \leq 10^6 $, n 为偶数。

思路：

把看题视作左括号，做题视作右括号，那么问题就转化成简单的括号匹配问题（比赛时没来得及看QWQ）。如果能匹配，那么就能得10分，否则只能得5分，栈模拟即可！

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1005;
string str; int cnt;
stack<char> st;
int main() {
    while(cin >> str) {
        while(!st.empty()) st.pop();
        cnt = 0;
        for(int i = 0; str[i]; ++i) {
            if(st.empty()) st.push(str[i]);
            else if(st.top() != str[i]) st.push(str[i]);
            else st.pop(), cnt ++;
        }
        cout << st.size() / 2 * 5 + cnt * 10 << endl;
    }
    return 0;
}

J.迷宫

题目描述

你在一个 n 行 m 列的网格迷宫中，迷宫的每一格要么为空，要么有一个障碍。
你当前在第 r 行第 c 列(保证该格子为空)。每次移动你可以向上下左右任意一个方向移动一格，前提是不能走到障碍上，也不能超出迷宫的边界。
你向左移动的次数不能超过 x 次，向右不能超过 y 次。
问在这种情况下，对于每个格子，是否存在一种移动方案让你走到它。
输出有多少个格子存在移动方案让你走到它。

输入描述:

第一行两个正整数 n,m 。
第二行两个正整数 r,c ，保证 $ 1 \leq r \leq n,1 \leq c \leq m $。
第三行两个整数 x,y ，保证 $ 0 \leq x,y \leq 10^9 $ 。
接下来 n 行，每行一个长度为 m 的字符串，
第 i 行第 j 个字符表示迷宫第 i 行第 j 列的格子，
字符为. 表示格子为空，字符为* 表示格子上有一个障碍。

输出描述:

输出一个数，表示有多少个格子存在移动方案让你走到它。

输入

4 5
3 2
1 2
.....
.***.
...**
*....

4 4
2 2
0 1
....
..*.
....
....

输出

10

7

说明

样例一：将能走到的格子用+标记：
+++..
+***.
+++**
*+++.
样例二：
.++.
.+*.
.++.
.++.

备注:

对于全部数据， $ 1 \leq n,m \leq 1000 $。

思路：

简单的bfs。从起点 $ (r,c) $ 向左或向右移动后到达的每个坐标点都被赋予2个已有的左移和右移状态量，求满足那些左移状态量不超过x，右移状态量不超过y的坐标点个数。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1005;
char mp[maxn][maxn];
int n, m, r, c, x, y, ans, dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, dist[maxn][maxn];
struct node{
    int dx, dy, gay_l, gay_r;
    node(int _x, int _y, int _gay_l, int _gay_r) : dx(_x), dy(_y), gay_l(_gay_l), gay_r(_gay_r) {}
};
queue<node> que;
bool check(int dxx, int dyy) {
    if(dxx < 0 || dyy < 0 || dxx >= n || dyy >= m ) return false;
    return true;
}
void bfs(int _x, int _y, int _gay_l, int _gay_r) {
    while(!que.empty()) que.pop();
    que.push(node(_x, _y, _gay_l, _gay_r));
    dist[_x][_y] = 0;
    while(!que.empty()) {
        node nod = que.front(); que.pop(), ans++;
        for(int i = 0; i < 4; ++i) {
            int nx = nod.dx + dir[i][0], ny = nod.dy + dir[i][1];
            if(check(nx, ny) && mp[nx][ny] != '*' && dist[nx][ny] > dist[nod.dx][nod.dy] + 1) {
                dist[nx][ny] = dist[nod.dx][nod.dy] + 1;
                if(i == 0 || i == 1) que.push(node(nx, ny, nod.gay_l, nod.gay_r));
                if(i == 2 && nod.gay_l < x) que.push(node(nx, ny, nod.gay_l + 1, nod.gay_r));
                if(i == 3 && nod.gay_r < y) que.push(node(nx, ny, nod.gay_l, nod.gay_r + 1));
            }
        }
    }
}
int main() {
    while(cin >> n >> m) {
        memset(dist, 0x3f, sizeof(dist));
        ans = 0;
        cin >> r >> c;
        cin >> x >> y;
        for(int i = 0; i < n; ++i) cin >> mp[i];
        bfs(r - 1, c - 1, 0, 0);
        cout << ans << endl;
    }
    return 0;
}