Iterovanie cez susedov

Pri grafových algoritmoch sa často stáva, že máme nejaký vrchol $(x,y)$

a potrebujeme niečo urobiť pre všetkých jeho susedov, prípadne pre všetkých jeho susedov spĺňajúcich určitú podmienku. Pri našej reprezentácii grafu by to mohlo vyzerať nasledovne:

if( /* TREBA SPRACOVAT VRCHOL (x+1, y) */ ) {
    /* SPRACUJ (x+1, y) */
}
if( /* TREBA SPRACOVAT VRCHOL (x, y+1) */ ) {
    /* SPRACUJ (x, y+1) */
}
if( /* TREBA SPRACOVAT VRCHOL (x-1, y) */ ) {
    /* SPRACUJ (x-1, y) */
}
if( /* TREBA SPRACOVAT VRCHOL (x, y-1) */ ) {
    /* SPRACUJ (x, y-1) */;
}

Takýto kód však nie je veľmi pekný a pri jeho písaní sa ľahko pomýlime. Ak pracujeme s mriežkou, kde má každý vrchol 8 susedov, je to ešte horšie.

Najčastejším zdrojom chýb pri tomto kuse kódu je, že sa pomýlime pri písaní +/- jednotiek. Tomuto sa dá elegantne vyhnúť tak, že tieto +/- jednotky vyextrahujeme do inej časti kódu. Vytvoríme si dve polia dX a dY, kde si budeme pamätať, čo potrebujeme pripočítať k súradniciam vrchola, aby sme dostali jeho susedov. Pri štvorcovej mriežke, kde má každý vrchol štyroch susedov, môžu vyzerať nasledovne:

int dX[4] = {1, 0, -1, 0};
int dY[4] = {0, 1, 0, -1};

Tieto dve polia majú nasledovný význam: prvý sused vrcholu (x,y) je vrchol (x+dX[0], y+dY[0]), druhý sused je (x+dX[1], y+dY[1]) atď.

Susedov teraz v programe nepotrebujeme vymenovať, ale môžeme ich spracúvať v cykle:

for(int smer=0; smer<4; smer++) {
    int nx = x+dX[smer], ny = y+dY[smer];
    if( /* TREBA SPRACOVAT VRCHOL (nx, ny) */ ) {
        /* SPRACUJ (nx, ny) */
    }
}

Tento kus kódu je omnoho menej náchylný na chyby. Ak je napríklad podmienka nejaký zložitý výraz, stačí ju napísať raz namiesto štyrikrát.