52 lines
1.2 KiB
Dart
52 lines
1.2 KiB
Dart
|
List<int>? bfsPath(int startDot, int goalDot) {
|
|||
|
|
if (startDot == goalDot) return [startDot];
|
|||
|
|
startDot--;
|
|||
|
|
goalDot--;
|
|||
|
|
List<List<int>>? graph = getLenTable();
|
|||
|
|
List<bool> used = <bool>[];
|
|||
|
|
List<int> dst = <int>[];
|
|||
|
|
List<int> pr = <int>[];
|
|||
|
|
|
|||
|
|
for (int i = 0; i < _amount; i++) {
|
|||
|
|
dst.add(-1);
|
|||
|
|
used.add(false);
|
|||
|
|
pr.add(0);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
List<int> q = <int>[];
|
|||
|
|
q.add(startDot);
|
|||
|
|
used[startDot] = true;
|
|||
|
|
dst[startDot] = 0;
|
|||
|
|
pr[startDot] = -1; //<2F> <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20><><EFBFBD> <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>.
|
|||
|
|
|
|||
|
|
while (q.isNotEmpty) {
|
|||
|
|
int cur = q.removeAt(0);
|
|||
|
|
int x = 0;
|
|||
|
|
for (int neighbor in graph![cur]) {
|
|||
|
|
if (neighbor != -1) {
|
|||
|
|
if (!used[x]) {
|
|||
|
|
q.add(x);
|
|||
|
|
used[x] = true;
|
|||
|
|
dst[x] = dst[cur] + 1;
|
|||
|
|
pr[x] = cur; //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
x++;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> <20><><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
List<int> path = <int>[];
|
|||
|
|
int cur = goalDot;
|
|||
|
|
path.add(cur + 1);
|
|||
|
|
while (pr[cur] != -1) {
|
|||
|
|
cur = pr[cur];
|
|||
|
|
path.add(cur + 1);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
path = path.reversed.toList();
|
|||
|
|
if (path[0] == (startDot + 1) &&
|
|||
|
|
path[1] == (goalDot + 1) &&
|
|||
|
|
!_dots[startDot].hasConnection(goalDot + 1)) return null;
|
|||
|
|
return path;
|
|||
|
|
}
|