codingblocks/Finding_Way_To_Zero.cpp at master · Aerma7309/codingblocks · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
* @Date    : 2020-05-11 10:16:23
* @Author  : Abhimanyu Kumar Maurya (aerma7309@gmail.com)
*/
#include <bits/stdc++.h>
using namespace std;

bool ib = ios_base::sync_with_stdio(0);
bool it = cin.tie(0);

bool Check(vector<int> &arr, vector<bool> &reach, int size, int pos)
{
    if (pos < 0 or pos >= size or arr[pos] == -1)
        return false;
    if (reach[pos])
        return true;
    if (arr[pos] == 0)
        return reach[pos] = true;
    int t = arr[pos];
    arr[pos] = -1;
    bool l = Check(arr, reach, size, pos - t);
    bool r = Check(arr, reach, size, pos + t);
    if (l or r)
        return reach[pos] = true;
    return false;
}

int main()
{
    int n, p;
    cin >> n >> p;
    vector<int> arr(n);
    vector<bool> canReach(n);
    for (auto &i : arr)
        cin >> i;
    bool flag = Check(arr, canReach, n, p);
    if (flag)
        cout << "true\n";
    else
        cout << "false\n";
}