while 루프로 반복적으로 코딩하는 부분을 변경하려고합니다.

Question

여기 내 코드가 있습니다.

#include <iostream> 
using namespace std; 

enum Direction { EAST, NORTH, WEST, SOUTH }; 
const int size = 12; 
int xStart = 2; int yStart = 0; 

char *maze2[ ] = { 
    "############", 
    "#...#......#", 
    "..#.#.####.#", 
    "###.#....#.#", 
    "#....###.#..", 
    "####.#.#.#.#", 
    "#..#.#.#.#.#", 
    "##.#.#.#.#.#", 
    "#........#.#", 
    "######.###.#", 
    "#......#...#", 
    "############", 
}; 
void printMaze (char maze[][ size ]); 
void mazeTraverse(char maze[][ size ], int x, int y, int direction); 

int main() 
{ 
    char maze[ size ][ size ]; 
    for (int x = 0; x < size; x++) 
     for (int y = 0; y < size; y++) 
      maze[ x ][ y ] = maze2[ x ][ y ]; 
    printMaze(maze); 
    mazeTraverse(maze, xStart, yStart, EAST); 
} 

void printMaze (char maze[][ size ]) 
{ 
    for (int x = 0; x < size; x++) 
    { 
     for (int y = 0; y < size; y++) 
      cout << maze[ x ][ y ]; 
     cout << endl; 
    } 
    cout << endl; 
    cout << "\nHit return to see next move\n"; 
    cin.get(); 
} 
bool validMove(char maze[][ size ], int x, int y) 
{ 
    return x >= 0 && x < size && y >= 0 && y < size && maze[x][y] != '#'; 
} 

bool coordsAreEdge(int x, int y) 
{ 
    return x== 0 || x== size - 1 || y == 0 || y== size - 1; 
} 

void mazeTraverse(char maze[][ size ], int x, int y, int direction) 
{ 
    maze[ x ][ y ] = 'x'; 
    printMaze(maze); 
    if (coordsAreEdge(x, y) && (x != xStart || y!= yStart)) 
    { 
     cout <<"\nMaze successfully exited!\n\n"; 
     return; 
    }else{ 
     for (int move = direction, count = 0; count < 4; 
      count++, move++, move %=4) 
     { 
      int nextX; int nextY; 
      switch (move) 
      { 
      case SOUTH: nextX = x + 1; nextY = y; break; 
      case EAST: nextX = x; nextY = y + 1; break; 
      case NORTH: nextX = x - 1; nextY = y; break; 
      case WEST: nextX = x; nextY = y - 1; break; 
      default: ; 
      } 
      if (validMove(maze, nextX, nextY)) 
      { 
       //Recursion move part 1 
       //mazeTraverse (maze, nextX , nextY, (move + 3)%4); 


       return; 
      } 
     } 
    } 
} 

나는 회귀 대신 mazeTraverse 함수를 while 루프로 만들려고 노력 중이며 막혔다.

Answer 1

트래버스가 어떻게 작동하는지 설명하면 좋을 것입니다. 내가 코드를 잘못 읽지 않는다면 기본적으로 #을 포함하지 않고 매트릭스 범위 내에있는 모든 위치에서 남쪽/동쪽/북쪽/서쪽으로 이동합니다.

당신은 BF 검색을 사용하여이 작업을 반복적으로 수행 할 수

: 매트릭스에 적용 http://en.wikipedia.org/wiki/Breadth-first_search 또는, 이명박 알고리즘 : http://en.wikipedia.org/wiki/Lee_algorithm 효율적으로 FIFO 큐를 사용하여 구현 될 수있다, 여기 수행하는 방법에 대해 설명합니다 Change FloodFill-Algorithm to get Voronoi Territory for two data points?

validMove 함수는 그대로 유지됩니다. 해당 위치가 유효한 경우에만 큐에 위치를 추가합니다. 기본적으로 모든 검사는 동일하게 유지됩니다. 단지 FIFO 대기열을 사용하여 암시 적 스택 대신 상태를 유지합니다.

Answer 2

구조체를 만들어 X, Y 및 방향 (호출간에 변경되는 세 가지)을 유지합니다. 우리는 구조체를 State이라고 부를 것입니다.

std::stack<State> 개체를 만듭니다. 변경하기 전에 X, Y, 방향의 현재 값을 스택에 밀어 넣고 작업 한 후에 팝업하십시오.

그러므로

while(.....) 
{ 
     push state 
     Do work of mazeTraverse 
     pop state 
} 

Answer 3

는 대신 표준 queue 및 while 루프를 사용하여 폭 우선 검색을 사용할 수 있습니다.

typedef pair<int, int> Point; 

queue<Point> path; 

Point start(xStart, yStart); 
path.push(start); 

const int move_x[] = {-1, 0, 1, 0}; 
const int move_y[] = {0, -1, 0, 1}; 

while (!path.empty()) 
{ 
    Point p = path.front(); 
    int x = p.first, y = p.second; 
    maze[x][y] = 'x'; 

    path.pop(); 

    if (coordsAreEdge(x,y) && p != start) 
    { 
    // Finished 
    break; 
    } 

    for (int i = 0; i < 4; ++i) 
    { 
    int newx = x + move_x[i]; 
    int newy = y + move_y[i]; 

    if (validMove(maze, newx, newy)) 
     path.push(Point(newx, newy)); 
    } 
} 

트릭을 수행해야합니다. 그것은 테스트되지 않은 것을 유의하십시오.

대신 A *를 사용하여 성능을 향상시킬 수 있지만 다소 복잡합니다. 이 코드에서 최단 경로를 찾아야하는지 알려주세요.

편집 : 당신이 stack에 queue을 변경 (및 path.top()에 path.front() 변경)하면 다음 코드가하는 일입니다 대신 깊이 우선 탐색 (DFS)를 얻을 것이다합니다. 그러나 DFS는 최단 경로를 찾지 못합니다 (필요한 경우).