Перейти к содержимому


* * * * * 2 Голосов

Поиск в глубину


Сообщений в теме: 2

#1 Санек

    Продвинутый пользователь

  • Администраторы
  • 41 сообщений
  • ГородВитебск

Отправлено 21 декабря 2011 - 18:18

Поиск в глубину, применяется для

*решения произвольных задач на графах, требующих соответствующего порядка обхода ("в глубину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)

*построения множества истоков и стоков (как истоков на транспонированном графе)

*построения сильносвязных компонент (ССК) графа ССК - это множество вершин, каждая из которых достижима из всех вершин ССК

Пример задачи на поиск в глубину.

Грядки

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные

В первой строке входного файла INPUT.TXT находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. (1 <= N, M <= 200)

Выходные данные

В выходной файл OUTPUT.TXT выведите количество грядок на садовом участке.

Примеры

INPUT.TXT

5 10

##......#.

.#..#...#.

.###....#.

..##....#.

........#.

OUTPUT.TXT

3

Основной код

var g:array [1..200,1..200] of char; k,i,j,n,m:integer;
procedure dfs(x,y:longint);
begin
g[x,y]:='o';
if (y<m )and(g[x,y+1]='#') then dfs(x,y+1);
if (y>1 )and(g[x,y-1]='#') then dfs(x,y-1);
if (x<n )and(g[x+1,y]='#') then dfs(x+1,y);
if (x>1 )and(g[x-1,y]='#') then dfs(x-1,y);
end;
begin
readln(n,m);
k:=0;
for i:=1 to n do begin
   				for j:=1 to m do
   				read(g[i,j]);
  readln;
end;
for i:=1 to n do
  for j:=1 to m do begin
                	if (g[i,j]='#')
 					then begin
       					k:=k+1;
       					dfs(i,j);
                      	end;
                	end;
writeln(k);
end.





#2 petuhovskiy

    Пользователь

  • Пользователи
  • PipPip
  • 16 сообщений
  • ГородВитебск

Отправлено 06 января 2012 - 19:25

Стандартный поиск в глубину
procedure DFS (v : longint);
var i : longint;
begin
	p[v]:=true;
	for i:=1 to n do if (a[v,i]=1)and(not(p[i])) then DFS(i);
end;

И ещё поиск в гллубину который находит кратчайший путь
procedure DFS (v,d : longint);
var i : longint;
begin
	p[v]:=d;;
	for i:=1 to n do if (a[v,i]=1)and((p[i]=-1)or(d+1<p[i])) then DFS(i,d+1);
end;

В этом алгоритме надо :
1. Забить массив p -1
2. Пускать глубину DFS(s,0);
Yo

#3 LVP

    Продвинутый пользователь

  • Администраторы
  • 180 сообщений
  • ГородВитебск

Отправлено 08 января 2012 - 20:03

Молодец, Артурчик!!!
Виктория Павловна





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных