Нэг зам руу аль болох гүн орж, гацвал буцсаар эхлэлээс хүрч болох бүх нүдийг тоолдог арга.

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

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

3×3 торын голд хана байна: ..., .#., .... S-ээс хэдэн нүдэнд хүрч болох вэ?

dfs(0, 0) баруун тийш (0, 1), (0, 2), доош (1, 2), (2, 2), зүүн тийш (2, 1), (2, 0), дээш (1, 0) гэж ханыг тойрон явна. 8 нүдэнд орсны дараа цааш шинэ нүд алга. Хариу 8.

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

Энгийн арга: S-ийг тэмдэглээд, "тэмдэгтэй нүдний хөрш бол тэмдэглэ" гэж бүх торыг дахин дахин гүйх. Өөрчлөлт гарахаа болитол давтана. Хамгийн муудаа R · C удаа гүйх тул O((R · C)²).

Гол санаа: шинэ нүдэнд ормогцоо түүний хөршүүд рүү шууд орох. dfs function нүдийг тэмдэглээд, очоогүй хөрш бүр дээр өөрийгөө дуудна. Гацвал recursion өөрөө өмнөх нүд рүү буцааж өгнө. Нүд бүрт нэг л удаа орно.

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

vis[r][c]
Нүдэнд аль хэдийн орсон эсэх.
cnt
Орсон нүдний тоо. Хариу нь энэ.
dfs(r, c)
Нүдэнд орж тэмдэглээд, очоогүй хөршүүд рүүгээ гүн орно.
Call stack
Дуусаагүй байгаа dfs дуудлагууд. Яг одоогийн замын нүднүүд.
connected component
Хоорондоо зам бүхий нүднүүдийн бүлэг (холбоотой хэсэг). dfs-ийг нэг удаа дуудахад нэг бүтэн component олдоно.
r\c012345670
S
1
2
3
4
5
E
cnt = 0
Call stack
хоосон

S нүднээс хэдэн нүдэнд хүрч болохыг тоолъё. DFS нэг зам руу аль болох гүн орно. Цааш явах газаргүй болбол буцаж ирээд өөр зам хайна.

Алхам 1 / 47
Хурд
  • Одоогийн нүд
  • Call stack-д байгаа (одоогийн зам)
  • Дууссан
  • Хүрэхгүй
  • Хана
Слайд 1 / 6

Гүн рүүгээ

Төөрдөг байшинд нэг зам руу аль болох гүн ороод, гацвал буцаж ирдэг. DFS яг ингэж ажилладаг.

dfs-grid.cpp
#include <bits/stdc++.h>
using namespace std;
int R, C, cnt;
string g[25];
bool vis[25][25];
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
void dfs(int r, int c) {
vis[r][c] = true;
cnt++;
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] == '#' || vis[nr][nc]) continue;
dfs(nr, nc);
}
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; i++) cin >> g[i];
dfs(0, 0);
cout << cnt << '\n';
return 0;
}

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

Тор дээр эхлэлээс хүрч болох нүднүүдийг олж, тоолно. Recursion ба буцах (backtracking) санааг graph дээр хэрэглэж, connected component (холбоотой хэсэг) гэж юу болохыг ойлгоно.

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

1. dfs(r, c): нүдийг очсон гэж тэмдэглээд cnt-г нэгээр нэмнэ. 2. Дээд, баруун, доод, зүүн хөршийг ээлжлэн шалгана. 3. Хөрш нь торны дотор, хана биш, очоогүй бол dfs-ийг тэр хөрш дээр дуудна. 4. Бүх хөрш дуусахад function дуусаж, өмнөх нүд рүүгээ буцна. 5. Хариу нь cnt, өөрөөр хэлбэл эхлэлээс хүрч болох нүдний тоо. Оролт: эхний мөрөнд R ба C, дараа нь R мөр тор: «.» бол зам, «#» бол хана. Эхлэл нь зүүн дээд булан.

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

vis нь нүдэнд хоёр дахь удаа орохыг хориглодог тул cnt давхар тоологдохгүй. S-ээс зам бүхий нүд бүрт хүрнэ: замын эхний нүд S-д орсон, зам дээрх нүдэнд орсон бол dfs түүний хөрш бүрийг шалгадаг тул дараагийнх нь ч орно.

Нүд бүрт нэг удаа орж, дөрвөн хөршийг шалгана: хугацаа O(R · C). Recursion-ий гүн хамгийн муудаа R · C хүрнэ. 1000×1000 тор дээр сая давхар Call stack болж програм унаж болзошгүй.

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

  • dfs-ийн эхэнд vis[r][c] = true хийхээ мартах. Хоёр хөрш нүд бие биеэ эцэс төгсгөлгүй дуудна.
  • Маш том тор дээр recursion ашиглах. Call stack хэтэрвэл өөрийн Stack ашигласан DFS эсвэл BFS бич.
  • Торны хүрээг шалгахгүй g[-1][c] уншиж буруу утга авах.

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

  • 1×1 тор: зөвхөн S, хариу 1.
  • S-ийн бүх хөрш хана: хариу 1.
  • Хана огт байхгүй: бүх нүдэнд хүрнэ, хариу R · C. 6×8 тор бол 48.

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

  1. Animation-ы жишээ тор дээр хариу хэд вэ?

    Хариу харах

    23. Хананы цаад талын нүднүүдэд хүрэхгүй.

  2. DFS ба BFS аль аль нь хүрч болох нүдний тоог зөв олох уу?

    Хариу харах

    Тийм. Хоёулаа хүрч болох нүд бүрт нэг удаа орно. Зөвхөн орох дараалал нь өөр.

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

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

  1. 1...., .#., ... тор дээр нүд бүрт хэд дэх удаад орсныг бич.

    Hint харах

    Чиглэлийн дараалал: дээш, баруун, доош, зүүн.

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

    Дээд мөр: 1, 2, 3. Дунд мөр: 8, хана, 4. Доод мөр: 7, 6, 5.

  2. 2.Торонд хэдэн тусдаа арал (connected component) байгааг тоол.

    Hint харах

    Бүх нүдийг гүйж, очоогүй нээлттэй нүд олдох бүрт dfs-ийг дууд.

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

    Хоёр давхар loop дотор if (g[r][c] == '.' && !vis[r][c]) { comps++; dfs(r, c); }. Хугацаа O(R · C) хэвээр.

  3. 3.Хамгийн том арлын хэмжээг ол.

    Hint харах

    dfs дуудахын өмнө cnt-г 0 болгоод, дууссаны дараа хамгийн ихийг хадгал.

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

    Арал бүрт cnt = 0; dfs(r, c); best = max(best, cnt);. Энэ нь paint програмын "бүх хэсгийг будах" (flood fill) хэрэгсэлтэй ижил санаа.

Жишээ

Оролт

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

Гаралт

23

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

Бодлого

Хичээл

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