매트릭스에서 bfs를 구현하는 방법은 무엇입니까?

Question

매트릭스에서 bfs를 구현하는 데 문제가 있습니다. 내 코드는 시작 노드의 자식 만 검사하는 것처럼 보입니다.

나의 목표는 'B'에서 'H'까지 최단 경로를 찾는 것입니다. 나는 또한 내 코드가 많은 수정이 필요하다고 생각한다. 미리 감사드립니다.

#include <iostream> 
#include <cstdio> 
#include <queue> 

using namespace std; 

int bfs(int, int); 

bool visited[100][100]; 
char matrica[100][100]; 

int m, n, d; 

int main() 
{ 

    scanf("%d %d", &m, &n); 

    for(int i = 0;i < m;i++){ 
     for(int j = 0; j < n; j++){ 
      cin >> matrica[i][j]; 
      visited[i][j] = false; 
     } 
    } 

    for(int i = 0;i < m;i++){ 
     for(int j = 0; j < n; j++){ 
      if(matrica[i][j] == 'B'){ 
       bfs(i, j); 
      } 
     } 
    } 

    cout << endl << d; 

    return 0; 
} 

int gk[] = {1, 0, -1, 0}; 
int gr[] = {0, 1, 0, -1}; 

int bfs(int x, int y){ 

    cout << endl; 

    queue<int>queue_x, queue_y; 
    int topx, topy, d=0; 

    //memset(visited, 0, sizeof visited); 

    visited[x][y] = true; 

    queue_x.push(x); 
    queue_y.push(y); 

    while(!queue_x.empty()){ 
     topx = queue_x.front(); 
     topy = queue_y.front(); 
     queue_x.pop(); 
     queue_y.pop(); 

     if(matrica[topx][topy] == 'H'){ 
      cout << endl << d << endl; 
      d++; 
      return d; 
     } 

     for(int i = 0; i < 4; i++){ 
      x += gk[i]; 
      y += gr[i]; 
      if(visited[x][y] == false && matrica[x][y] != '#'){ 
       visited[x][y] = true; 
       matrica[x][y] = '*'; 
       queue_x.push(x); 
       queue_y.push(y); 
       d++; 

       //------------- 
       for(int i = 0; i < m;i++){ 
        for(int j = 0; j < n;j++){ 
         cout << matrica[i][j]; 
        } 
        cout << endl; 
       } 
       //------------- 
      } 
     } 
    } 
} 

입/출력 :

입력 :

5 
5 
##### 
#..B# 
#...# 
#...# 
###H# 

출력 :

##### 
#..B# 
#...# 
#...# 
###H# 
0 

Answer 1

변수 x 및 y

x += gk[i]; 
y += gr[i]; 

은 한 반복에서 다음 반복까지의 값을 "기억하지"않아야합니다.

변경

이러한 라인은

x = topx + gk[i]; 
y = topy + gr[i];