回溯 羅密歐與朱麗葉

問(wèn)題

羅密歐與朱麗葉的迷宮問(wèn)題 ，回溯法實(shí)現(xiàn)。

【問(wèn)題描述】羅密歐與朱麗葉的迷宮。羅密歐與朱麗葉身處一個(gè)m×n的迷宮中，如圖所示。每一個(gè)方格表示迷宮中的一個(gè)房間。這m×n個(gè)房間中有一些房間是封閉的，不允許任何人進(jìn)入。在迷宮中任何位置均可沿8 個(gè)方向進(jìn)入未封閉的房間。羅密歐位于迷宮的(p，q)方格中，他必須找出一條通向朱麗葉所在的(r，s)方格的路。在抵達(dá)朱麗葉之前，他必須走遍所有未封閉的房間各一次，而且要使到達(dá)朱麗葉的轉(zhuǎn)彎次數(shù)為最少。每改變一次前進(jìn)方向算作轉(zhuǎn)彎一次。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法幫助羅密歐找出這樣一條道路。

解法

#pragma warning(disable:4996)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
using namespace std;
int n, m, k;
int map[105][105];
int path[105 * 105];
int best[105 * 105];
int dx[] = { 0,0,1,-1,1,1,-1,-1 };
int dy[] = { 1,-1,0,0,1,-1,-1,1 };
int p, q, r, s;
int minturn = 0x3f3f3f3f;
int num = 0;
void backtrack(int x, int y, int cur)
{
    if (cur >= n * m - k)
    {
        if (x != r || y != s)  return;
        int turn = 0;
        for (int i = 2; i < cur; i++)
            if (path[i] != path[i - 1])   turn++;
        if (turn < minturn)
        {
            memcpy(best, path, sizeof(path));
            minturn = turn;
            num = 1;
        }
        else if (turn == minturn)   num++;
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (map[xx][yy] == -1)  continue;
        if (xx<1 || xx>n || yy<1 || yy>m)  continue;
        path[cur] = i;
        map[xx][yy] = -1;
        backtrack(xx, yy, cur + 1);
        map[xx][yy] = 0;
    }
}
void path_solve()
{
    int x = p, y = q;
    map[p][q] = 1;
    for (int i = 1; i < n * m - k; i++)
    {
        int xx = x + dx[best[i]];
        int yy = y + dy[best[i]];
        map[xx][yy] = map[x][y] + 1;
        x = xx;
        y = yy;
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        map[x][y] = -1;
    }
    scanf("%d%d%d%d", &p, &q, &r, &s);
    map[p][q] = -1;
    backtrack(p, q, 1);
    path_solve();
    printf("%d\n%d\n", minturn, num);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (j != 1)   printf(" ");
            printf("%d", map[i][j]);
        }
        printf("\n");
    }
}