Help in BFS! - Codeforces

Блог пользователя bhayanak

Help in BFS!

Автор bhayanak, история, 7 лет назад, По-английски

i want an help beecause it is a difficult questions (sorry for mine poor english)

https://www.codechef.com/problems/DIGJUMP

bhayanak
7 лет назад
1

Комментарии (1)

Написать комментарий?

Flyce

7 лет назад, # |

You can make graph with edges between i and i + 1. Also when you visit some verix u with digit x, and you haven't visited any other vertix with the same digit, you can push all of them into the queue, setting the distance to them dst[u] + 1.

Code

#include <bits/stdc++.h>

using namespace std;
int input(){
    int res = 0; char c = ' ';
    while (c < '0') c = getchar();
    while (c >= '0') res = res * 10 + (c - '0'), c = getchar();
    return res;
}
const int N = 1e5 + 1;

int n, d[N], a[N];
char c[10];
vector <int> idx[10], g[N];
int main(){
    string s; cin >> s;
    for (auto i : s)
        idx[a[n] = i - '0'].push_back(n), ++ n;
    for (int i = 1; i < n; ++ i)
        d[i] = 1e9;
    queue <int> q; q.push(0);
    while (q.size()){
        int u = q.front(); q.pop();
        for (int v = max(0, u - 1); v <= min(n - 1, u + 1); ++ v){
            if (d[v] == 1e9){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
        if (!c[a[u]])
            for (auto v : idx[a[u]])
                if (d[v] == 1e9){
                    d[v] = d[u] + 1;
                    q.push(v);
                }
        c[a[u]] = 1;
    }
    cout << d[n - 1];
}

→ Ответить