DFS Kullanılarak Örnek Soru Çözümü
Posted On April 2, 2019
https://www.spoj.com/problems/ABCPATH/
#include <bits/stdc++.h>
#define MAXEDGE 100
using namespace std;
char grid[55][55];
bool vis[55][55];
int h, w;
/*
Bu problemde çizgemizi h'ye w'lik 2 boyutlu bir dizi şeklinde
tutuyoruz.
Bu durumda toplam düğüm sayımız h*w olur. grid[i][j] düğümününde i-j
düğümünün tuttuğu char değeri saklanır. Aynı zamanda i-j düğümünün
komşuları (i-1)-j, (i-1)-(j-1), (i-1)-(j+1), (i+1)-j, (i+1)-(j-1),
(i+1)-(j+1), i-(j-1) ve i-(j+1) olur.
*/
bool check(char c, int a, int b){
if( a >= 0 && a < h && b >= 0 && b < w && grid[a][b] == c+1 && vis[a][b] == 0)
return 1;
else
return 0;
}
/*
check fonksiyonu, dfs sırasında a-b düğümüne ilerlenip ilerilmemesi
gerektiğini kontrol eder.
Eğer a-b düğümü işaretli değilse, a ve b sınır değerleri içinde
kalıyorsa ve grid[a][b] değeri şu anda bulunduğumuz düğümün char
değerinden bir fazlaysa 1, aksi durumda 0 döndürür.
*/
int dfs(int x, int y){
int add = 0;
char tmp = grid[x][y];
vis[x][y] = 1;
if(check(tmp, x-1, y))
add = max(add, dfs(x-1, y));
if(check(tmp, x-1, y-1))
add = max(add, dfs(x-1, y-1));
if(check(tmp, x-1, y+1))
add = max(add, dfs(x-1, y+1));
if(check(tmp, x+1, y+1))
add = max(add, dfs(x+1, y+1));
if(check(tmp, x+1, y-1))
add = max(add, dfs(x+1, y-1));
if(check(tmp, x+1, y))
add = max(add, dfs(x+1, y));
if(check(tmp, x, y-1))
add = max(add, dfs(x, y-1));
if(check(tmp, x, y+1))
add = max(add, dfs(x, y+1));
/*
Sırayla x-y düğümünün bütün komşuları incelenir ve uygun durumda
olanlara dfs fonksiyonu çağrılır. Burada dfs fonksiyonunun
döndürdüğü değer o düğümden dfs atıldığında gezilebilecek maksimum
düğüm sayısıdır. Her dfs fonksiyonu için döndürülen değer,
komşularının dfs fonksiyonlarından maksimum olanın bir fazlasıdır.
*/
return (add+1);
}
int main(){
int count = 1;
while(1){
cin >> h >> w;
if(h == 0 && w == 0)
return 0;
for(int i = 0; i < h; ++i)
for(int j = 0; j < w; ++j){
cin >> grid[i][j];
vis[i][j] = 0;
}
int ans = 0;
for(int i = 0; i < h; ++i)
for(int j = 0; j < w; ++j)
if(grid[i][j] == 'A')
ans = max(ans, dfs(i, j));
/*
Oluşturacağımız harf dizisi her türlü 'A' harfinden
başlayacağı için 'A' değerini tutan bütün düğümlere
dfs atılır.Aralarından en büyüğü cevabımızı verir
*/
cout << "Case " << count++ << ": " << ans << endl;
}
}