Алгоритм DFS последовательно находит путь с меньшим количеством вершин, чем максимум - PullRequest
Новая
       30

Алгоритм DFS последовательно находит путь с меньшим количеством вершин, чем максимум

0 голосов
/ 19 апреля 2020

Я решаю проблему программирования с помощью dfs. Tldr выглядит следующим образом: в координатах x, y есть n коров. Они могут общаться с другими людьми в пределах своего радиуса «голоса» с. То, что корова a может общаться с коровой b, не означает, что b может общаться обратно, если ей не хватает p. Если сообщение начинается с какой-либо коровы, какое наибольшее количество коров оно сможет достичь? Коровы могут передавать сообщения от одного к другому. Ex. Если b может слышать a, а c не слышит a, но слышит b, b может передавать информацию от a до c, поэтому 3 коровы слышат информацию в этом случае. Вот пример ввода: 

4
1 3 5
5 4 3
7 2 1
6 1 1

Первая строка - N, следующие строки - коровы x, y и p. Вот мой код: 

#include <iostream>
#include <cmath>
using namespace std;
int n;
int best=0;
int cnt=1;
struct cow {
    int x, y, p;
    bool visited=0;
} cows[201];
bool adj[201][201];
bool access (int a, int b) {
    return pow(cows[b].x-cows[a].x, 2)+pow(cows[b].y-cows[a].y, 2)<=pow(cows[a].p, 2);
}
void dfs(int cow1) {
    for (int i=1; i<=n; i++) {
        if (cnt>best)
        best=cnt;
        if ((!cows[i].visited)&&(adj[cow1][i])) {
            cnt=cnt+1;
            cows[i].visited=1;
            dfs(i);
        }
    }
    return;
}

int main () {
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>cows[i].x>>cows[i].y>>cows[i].p;
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i!=j) {
            if(access(i, j)) {
                adj[i][j]=1;
            }
            else {
                adj[i][j]=0;
            }
        }
        }
    }
    for (int i=1; i<=n; i++) {
        cows[i].visited=1;
        dfs(i);
        cnt=1;
        for (int j=1; j<=n; j++) {
            cows[j].visited=0;
        }
    }
    cout<<best;
}

Я не совсем уверен, где проблема, но я уверен, что это в функции dfs, а не в создании списка смежности. Мой код работает только для примера. По сути, я делаю DFS для всех n случаев запуска коров для сообщения.

1 Ответ

0 голосов
/ 19 апреля 2020

Ошибка проста. Вы измеряете самую длинную длину пути (на самом деле количество коров). Но вопрос в том, как коровы могут быть доступны. Рассмотрим случай с тремя коровами, из которых одна может быть услышана всеми, в то время как другие не имеют голоса. Ваша программа ответит 2 (если я не пропустил еще одну ошибку), так как это самая длинная цепочка, но правильный ответ - 3 (это количество коров visited).

...