Хана бүхий тор дээр эхлэлээс долгион шиг тархаж, төгсгөл хүртэлх хамгийн цөөн алхмыг олдог арга.

IntermediateХугацаа: O(R · C)Санах ой: O(R · C)
HackerRank дээр бодох

Эхлээд жижиг бодлого

3×3 торын голд хана байна: ..., .#., .... S нь зүүн дээд (0, 0), E нь баруун доод (2, 2) булан. Хамгийн цөөндөө хэдэн алхмаар хүрэх вэ?

S-д 0 гэж бичнэ. Хөрш (0, 1) ба (1, 0) нүдэнд 1, тэдний шинэ хөршүүдэд 2, дараа нь 3. E-д 4 гэж бичигдэнэ. Хариу 4.

Энгийн аргаас санаа руу

Энгийн арга бол S-ээс эхэлсэн бүх замыг туршаад хамгийн богинохыг нь сонгох. Гэтэл замын тоо торны хэмжээнээс хамааран маш хурдан өсдөг. 10×10 тор дээр ч замын тоо тэрбумаас хамаагүй олон.

Гол санаа: нүднүүдийг S-ээс хэр хол байгаагаар нь давхарлан нээх. Эхлээд 1 алхамд хүрэх бүх нүдийг, дараа нь 2 алхамд хүрэхийг нээнэ. Үүнийг Queue хийж өгнө: түрүүлж нээсэн нүд түрүүлж гарч, хөршүүдээ нээнэ. Ингэвэл нүдэнд анх хүрсэн мөчийн зай нь хамгийн бага зай болно.

Нэр томьёо ба тэмдэглэгээ

d[r][c]
(r, c) нүдэнд хэдэн алхмаар хүрснийг хадгална. -1 бол хараахан хүрээгүй.
q
Нээгдсэн боловч хөршүүдээ хараахан шалгаагүй нүднүүдийн Queue.
dr[k], dc[k]
Дөрвөн чиглэл: дээш, баруун, доош, зүүн.
R, C
Торны мөр ба баганын тоо.
r\c012345670
S
1
2
3
4
5
E
q (Queue)
хоосон

S нүднээс E нүд хүртэлх хамгийн цөөн алхамтай замыг олъё. S нь зүүн дээд, E нь баруун доод буланд байна. Хар нүд бол хана. Нүд бүрт хэдэн алхмаар хүрснийг бичнэ.

Алхам 1 / 49
Хурд
  • Одоогийн нүд
  • Шинээр олдсон
  • Queue-д байгаа
  • Шалгаж дууссан
  • Хамгийн богино зам
  • Хана
Слайд 1 / 7

Долгион шиг тархана

Усанд чулуу шидэхэд долгион бүх тийшээ жигд тархдаг. BFS ч эхлэлээсээ эхлээд ойрын нүднүүд рүү, дараа нь холынх руу тархана.

bfs-grid.cpp
#include <bits/stdc++.h>
using namespace std;
int R, C, d[25][25];
string g[25];
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
queue<pair<int, int>> q;
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++) cin >> g[i];
memset(d, -1, sizeof d);
d[0][0] = 0;
q.push({0, 0});
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (g[nr][nc] == '#' || d[nr][nc] != -1) continue;
d[nr][nc] = d[r][c] + 1;
q.push({nr, nc});
}
}
cout << d[R - 1][C - 1] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Тор, газрын зураг дээрх хамгийн богино замыг олно. Олимпиадад «хамгийн цөөн алхам», «хамгийн богино зам» гэсэн бодлогыг ихэвчлэн ингэж боддог.

Яаж ажилладаг вэ?

1. Бүх нүдэнд d = -1 (хүрээгүй) гэж бичнэ. Эхлэлд d = 0 гэж бичээд Queue-д хийнэ. 2. Queue-гийн эхнээс нүд гаргана. 3. Түүний дээд, баруун, доод, зүүн хөршөөс хана биш, d = -1 байгаа бүрт d + 1 гэж бичээд Queue-гийн ард нэмнэ. 4. Queue хоосортол давтана. Ойрын нүд үргэлж түрүүлж гардаг тул d бүр хамгийн цөөн алхам болно. 5. Хариу нь төгсгөлийн d. Хүрэхгүй бол -1. Оролт: эхний мөрөнд R ба C, дараа нь R мөр тор: «.» бол зам, «#» бол хана. Эхлэл нь зүүн дээд, төгсгөл нь баруун доод булан.

Яагаад зөв, хэр хурдан бэ?

Queue-д нүднүүд зай нь буурахгүй дарааллаар ордог: эхлээд бүх 0, дараа нь бүх 1, дараа нь бүх 2. Тиймээс нүдэнд анх хүрэх үед түүнд хүрэх илүү богино зам аль хэдийн шалгагдсан байх ёстой. Тэр зам байсан бол нүд өмнө нь нээгдэх байсан. Тиймээс d бүр хамгийн цөөн алхам.

Нүд бүр Queue-д нэг л удаа орж, дөрвөн хөршөө шалгана: хугацаа O(R · C). 1000×1000 тор бол сая нүд, 4 сая орчим шалгалт, нэг секундэд амжина. d array O(R · C) санах ой эзэлнэ.

Түгээмэл алдаа

  • Нүдийг Queue-гээс гаргах үед биш, Queue-д хийх үед тэмдэглэх ёстой. Эс бол нэг нүд Queue-д олон удаа орж удаашрах эсвэл буруу зай гарна.
  • Торноос гарсныг шалгахаас өмнө g[nr][nc]-г унших. Кодонд эхлээд хүрээг, дараа нь ханыг шалгадаг.
  • d-г -1-ээр эхлүүлэхээ мартах. 0 гэж эхлүүлбэл бүх нүд аль хэдийн хүрсэн мэт харагдана.
  • Хамгийн богино замыг DFS-ээр хайх. DFS олсон зам заавал хамгийн богино биш.

Хязгаарын тохиолдол

  • 1×1 тор: эхлэл, төгсгөл нэг нүд, хариу 0.
  • Хана замыг бүрэн хаасан: Queue хоосортол E-д хүрэхгүй, хариу -1.
  • Хана огт байхгүй: хариу R − 1 + C − 1. 6×8 тор бол 12.

Өөрийгөө шалга

  1. Яагаад Stack биш Queue ашигладаг вэ?

    Хариу харах

    Queue ойрын нүдийг түрүүлж гаргадаг тул нүднүүд зайныхаа дарааллаар нээгдэнэ. Stack бол нэг зүг рүү гүн орж, зай буруу гарна.

  2. .#., #.., ... тор дээр хариу юу вэ?

    Хариу харах

    -1. S-ийн баруун ба доод хөрш хоёулаа хана.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1...#., .##., .... тор дээр нүд бүрийн d-г бич. E-д хэдэн алхмаар хүрэх вэ?

    Hint харах

    Зүүн баганаар доошоо, дараа нь доод мөрөөр баруун тийш явна.

    Хариу ба тайлбар

    Доод мөр: 2, 3, 4, 5. Баруун багана дээшээ: 6, 7. E нь (2, 3) тул хариу 5.

  2. 2.Хамгийн богино замын нүднүүдийг хэвлэ.

    Hint харах

    Нүд нээх бүрт хаанаас ирснийг par[nr][nc] = {r, c} гэж хадгал.

    Хариу ба тайлбар

    E-гээс эхлээд par-ыг дагаж S хүртэл ухарна. Цуглуулсан нүднүүдийг урвуулж хэвлэнэ. Хугацаа O(R · C) хэвээр.

  3. 3.Тор дээр хэд хэдэн галын эх үүсвэр "F" байна. Нүд бүрт гал хэдэн минутад хүрэхийг ол. Минут бүрт гал хөрш рүү тархана.

    Hint харах

    Эхлэх үед бүх F-ийг 0 зайтайгаар Queue-д хий.

    Хариу ба тайлбар

    Бүх F-д d = 0 бичээд Queue-д хийнэ. Дараа нь ердийн BFS. Үүнийг multi-source BFS гэдэг. Хугацаа O(R · C).

Жишээ

Оролт

6 8
...#.###
.#.###..
.#...###
.###...#
...#.#.#
##...#..

Гаралт

12

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.