(关键词-dfs搜索)

Question

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <conio.h>
#include <windows.h>
using namespace std;
const int R = 15;
const int C = 15;
const char W = '#';
const char L = ' ';
const char S = 'S';
const char E = 'E';
const char P = 'A';
char m[R][C];
bool visited[R][C];
int step = -1;
void filll(int Foreground_color, int Background_color) {
    WORD wColor = ((Background_color & 0x0F) << 4) + (Foreground_color & 0x0F);
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), wColor);
}
void init(){
    for (int i = 0; i < R; i ++) {
        for (int j = 0; j < C; j ++) {
            if (i == 0 || i == R - 1 || j == 0 || j == C - 1) {
                m[i][j] = W;
            } else {
                m[i][j] = L;
            }
        }
    }
    for (int i = 2; i < R - 2; i += 2) {
        for (int j = 2; j < C - 2; j += 2) {
            m[i][j] = W;
            int dir = rand() % 4;
            switch (dir) {
                case 0: 
                    if (m[i - 1][j] == L) {
                        m[i - 1][j] = W;
                    }
                    break;
                case 1: 
                    if (m[i + 1][j] == L) {
                        m[i + 1][j] = W;
                    }
                    break;
                case 2: 
                    if (m[i][j - 1] == L) {
                        m[i][j - 1] = W;
                    }
                    break;
                case 3:
                    if (m[i][j + 1] == L) {
                        m[i][j + 1] = W;
                    }
                    break;
            }
        }
    }
    m[1][1] = S;
    m[R - 2][C - 2] = E;
}
void print(){
    for (int i = 0; i < R;i ++) {
        for (int j = 0; j < C; j ++) {
            cout << m[i][j] << " ";
        }
        cout << endl;
    }
}
bool move(int& r, int& c, char d){
    int nr = r, nc = c;
    switch (d) {
        case 'w':
        case 'W':
            nr --;
            break;
        case 's':
        case 'S':
            nr ++;
            break;
        case 'a':
        case 'A': 
            nc --;
            break;
        case 'd':
        case 'D': 
            nc ++;
            break;
    }
    if (m[nr][nc] == L or m[nr][nc] == E) {
        m[r][c] = L;
        r = nr;
        c = nc;
        m[r][c] = P;
        if(nr == R - 2 and nc == C - 2)    return true;
    }
    return false; 
}
void dfs(int r, int c, int steps) {
    if (r < 1 || r > R - 2 || c < 1 || c > C - 2 || visited[r - 2][c - 2] || m[r - 2][c - 2] == '#') {
        return;
    }
    if (r == R - 2 && c == C - 2) {
        if (step == -1 || steps < step) { 
            step = steps;
        }
        return;
    }
    visited[r - 2][c - 2] = true;
    dfs(r - 1, c, steps + 1);
    dfs(r + 1, c, steps + 1);
    dfs(r, c - 1, steps + 1);
    dfs(r, c + 1, steps + 1);
    visited[r - 2][c - 2] = false;
}
int main(){
    int r = 1, c = 1; 
    char d;
    srand(time(NULL));
    init();
    m[r][c] = P;
    while (true) {
        system("cls"); 
        filll(14,0);
        cout << "           走迷宫           " << endl << endl; 
        filll(2,15);
        print();
        filll(12,0);
        cout << "tip:使用WASD移动。按Q退出。" << endl;
        d = getch();
        dfs(r,c,0);
        if (d == 'q' || d == 'Q') {
            break;
        }
        if (move(r,c,d)) {
            system("cls");
            filll(14,0);                
            cout << "祝贺你赢了!最短步数为" << step;
            //system("pause");
            system("pause");
            filll(15,0);
            return 0;
        }
    }
    return 0;
}

dfs搜索最短步数不对，请问如何修改

Answer 1

void dfs(int r, int c, int steps) {
    if (r < 0 || r >= R || c < 0 || c >= C || visited[r][c] || m[r][c] == W) {
        return;
    }
    if (r == R - 2 && c == C - 2) {
        if (step == -1 || steps < step) { 
            step = steps;
        }
        return;
    }
    visited[r][c] = true;
    dfs(r - 1, c, steps + 1);
    dfs(r + 1, c, steps + 1);
    dfs(r, c - 1, steps + 1);
    dfs(r, c + 1, steps + 1);
    visited[r][c] = false;
}

if (move(r,c,d)) {
    dfs(1, 1, 0);
    system("cls");
    filll(14,0);                
    cout << "祝贺你赢了!最短步数为" << step;
    system("pause");
    filll(15,0);
    return 0;
}