Кратчайший путь через несколько точек [C++]

Дана сетка, в которой содержимое каждой ячейки может быть

X: "стена"

H: "контрольная точка" (не более 5)

G: начальная позиция (ровно одна)

Мне нужно найти минимальное количество ходов, необходимое для прохождения всех контрольных точек (H), начиная с Г. Отдельные движения могут быть горизонтальными или вертикальными, хотя диагональное движение может быть достигнуто путем объединения горизонтальных и вертикальных движений. Переход за пределы сетки или к стенам (X) невозможен.

Для сетки

    ..H..
    ..X.H
    G...X

ожидаемый ответ: 7.

Количество строк и столбцов в сетке может быть не более 20.

Я попытался написать код bfs для решения проблемы, но при тестировании с сеткой выше он выдал 6, что неверно.

Я не знаю, что я делаю неправильно. Может ли кто-нибудь помочь?

#include <iostream>
#include &lt;bits/stdc++.h>
#include &lt;algorithm>
#include &lt;cstdio>
#include &lt;stdlib.h>
#include &lt;cmath>
#include &lt;cstring>
#include &lt;math.h>
#include &lt;string>
#include &lt;sstream>
#include &lt;vector>
#include &lt;iomanip>
#include &lt;deque>
#include &lt;queue>

#define loop(i, n) for(int i = 0; i < n; i++)  
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0' < (_=getchar());x=(x<<3)+(x<<1)+_-'0');}while(0)  
#define ull unsigned long long  

char _;

using namespace std;
typedef pair <int, int> ipair;

int rows, columns, startx, starty, hiders;

char grid[20][20];
char buffer[255];

bool valid(int x, int y){  
    if(x >= 0 && x < rows && y >= 0 && y < columns && grid[x][y] != 'X')  
        return true;  
    return false;  
}  

int main(){  
    scanf("%i%i%i", &rows, &columns, &hiders);  

    //this is where I set up the grid, at put it in the grid array.  

    for(int i = 0; i < rows; i++){  
        scanf("%s", &buffer);  
        for(int j = 0; j < columns; j++){  
            if(buffer[j] == 'G'){  
                startx = i;  
                starty = j;  
            }  
            grid[i][j] = buffer[j];  
        }  
    }  

    queue<ipair> Q; //keeps track of positions  
    queue<int> DQ; //keeps track of distance  
    int found = 0; //how many checkpoints are found  

    Q.push(make_pair(startx, starty)); //push start pos  
    DQ.push(0);  

    while(!Q.empty()){  
        int x = Q.front().first; //check x  
        int y = Q.front().second; //check y  

        if(found == hiders){ //if we found the amount needed  
            printf("%i", DQ.front()); // print current distance  
            return 0;  
        }  

        if(grid[x][y] == 'H'){ //found checkpoint  
            found++; //found a hider  
        }  
        //if it's possible to move right  
        if(valid(x + 1, y)){  
            Q.push(make_pair(x+1, y));  
            DQ.push(DQ.front() + 1);  
        }  
        //if it's possible to move left  
        if(valid(x - 1, y)){  
            Q.push(make_pair(x-1, y));  
            DQ.push(DQ.front() + 1);  
        }  
        //if it's possible to move up  
        if(valid(x, y + 1)){  
            Q.push(make_pair(x, y + 1));  
            DQ.push(DQ.front() + 1);  
        }  
        //if it's possible to move down  
        if(valid(x, y - 1)){  
            Q.push(make_pair(x, y - 1));  
            DQ.push(DQ.front() + 1);  
        }  

        Q.pop();  
        DQ.pop();  
        grid[x][y] = 'X'; //set the current coordinates as visited/walls  
    }  
}