blue cell: obstacles, black cell = start( or end) 

$$\text{distance measure}:~\text{Manhattan distance}=|x_2 - x_1 | + |y_2 - y_1|$$

Grassfire 알고리즘을 써서 최단경로를 찾는 문제는 DFS로도 구현할 수 있으나 비효율적이고(왜 그런지는 쉽게 알 수 있다) BFS로 구현하는 것이 더 적합하다. 

void grassfire(CPoint q, int **map, int w, int h, int **dist) {
    for (int y = 0; y < h; y++) 
        for (int x = 0; x < w; x++) 
            dist[y][x] = INF;  //unvisited cells;

    std::queue<CPoint> Q;
    dist[q.y][q.x] = 0;     //start( or end) position: distance = 0;
    Q.push(q);
    while (!Q.empty()) {
        CPoint p = Q.front(); Q.pop();
        int distance = dist[p.y][p.x];
        if (p.x > 0     && map[p.y][p.x - 1] == 0 && dist[p.y][p.x - 1] == INF) {
            dist[p.y][p.x - 1] = distance + 1;
            Q.push(CPoint(p.x - 1, p.y)); 
        }
        if (p.x < w - 1 && map[p.y][p.x + 1] == 0 && dist[p.y][p.x + 1] == INF) {
            dist[p.y][p.x + 1] = distance + 1;
            Q.push(CPoint(p.x + 1, p.y));
        }
        if (p.y > 0     && map[p.y - 1][p.x] == 0 && dist[p.y - 1][p.x] == INF) {
            dist[p.y - 1][p.x] = distance + 1;
            Q.push(CPoint(p.x, p.y - 1));
        }
        if (p.y < h - 1 && map[p.y + 1][p.x] == 0 && dist[p.y + 1][p.x] == INF) {
            dist[p.y + 1][p.x] = distance + 1;
            Q.push(CPoint(p.x, p.y + 1));
        }
    }
}
728x90

'Image Recognition > Fundamental' 카테고리의 다른 글

Brute-Force Euclidean Distance Transform  (0) 2021.03.14
Poisson Noise  (0) 2021.03.06
Image Sharpness  (0) 2021.02.25
Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Posted by helloktk
,