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;
    }
}