實驗名：羅密歐與朱麗葉的迷宮問題 實驗內容： 問題描述： 羅密歐與朱麗葉的迷宮。羅密歐與朱麗葉身處一個m×n的迷宮中，如圖所示。每一個方格表示迷宮中的一個房間。這m×n個房間中有一些房間是封閉的，不允許任何人進入。在迷宮中任何位置均可沿8 個方向進入未封閉的房間。羅密歐位于迷宮的(p，q)方格中，他必須找出一條通向朱麗葉所在的(r，s)方格的路。在抵達朱麗葉之前，他必須走遍所有未封閉的房間各一次，而且要使到達朱麗葉的轉彎次數為最少。每改變一次前進方向算作轉彎一次。請設計一個算法幫助羅密歐找出這樣一條道路。 羅密歐與朱麗葉的迷宮 .編程任務： 對于給定的羅密歐與朱麗葉的迷宮，編程計算羅密歐通向朱麗葉的所有最少轉彎道路。 .數據輸入： 由文件input.txt給出輸入數據。第一行有3個正整數n，m，k，分別表示迷宮的行數，列數和封閉的房間數。接下來的k行中，每行2 個正整數，表示被封閉的房間所在的行號和列號。最后的2 行，每行也有2 個正整數，分別表示羅密歐所處的方格(p，q)和朱麗葉所處的方格(r，s)。 .結果輸出: 將計算出的羅密歐通向朱麗葉的最少轉彎次數和有多少條不同的最少轉彎道路輸出到文件output.txt。文件的第一行是最少轉彎次數。文件的第2 行是不同的最少轉彎道路數。接下來的n行每行m個數，表示迷宮的一條最少轉彎道路。A[i][j]=k表示第k步到達方格(i,j)；A[i][j]=-1 表示方格(i,j)是封閉的。 如果羅密歐無法通向朱麗葉則輸出“No Solution!”。 輸入文件示例 input.txt 3 4 2 1 2 3 4 1 1 2 2 輸出文件示例 output.txt 6 7 1 -1 9 8 2 10 6 7 3 4 5 -1
1 回答
一只甜甜圈
TA貢獻1836條經驗 獲得超5個贊
#include <iostream>
#include <fstream>
using namespace std;
struct RZMaze
{
protected:
static int dir[8][2]; //8個方向
int n, m, k; //行數、列數、封閉房間數
int Romeo[2]; //Romeo所在的位置
int Juliet[2]; //Juliet所在的位置
int **maze; //迷宮數組
int **bestx; //保存最優解
int bestc; //保存最優值
int dirs; //當前拐彎次數
int bccount; //最優解的個數
public:
RZMaze(int nn, int mm, int kk); //構造函數 //給所有的方格標記
~RZMaze(); //析構函數
bool InMaze(int x, int y); //判斷坐標(x,y)是否還在迷宮內
void Backtrack(int dep, int x, int y, int di); //遞歸回溯 走過多少個字 已經拐了多少彎
void ReadData(fstream &fileIn); //從文件中讀入數據
//先讀封閉房間的行號和列號寫入r,c
void SaveSol(); //保存當前解為最優解
void Process(); //處理函數
void Output(fstream &fileOut); //將計算結果輸出到文件中
};
//初始化8個方向的偏移量
int RZMaze::dir[8][2] = {{-1, 0},{-1,1},{0, 1},{1, 1},
{1, 0}, {1, -1}, {0, -1}, {-1, -1}};
RZMaze::RZMaze(int nn, int mm, int kk)
{
int i, j;
n= nn; m = mm; k = kk;
maze = new int* [n];
for(i = 0; i < n; i++) maze[i] = new int [m];
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++) maze[i][j] = 0;
}
bestx = new int* [n];
for(i = 0; i < n; i++) bestx[i] = new int [m];
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++) bestx[i][j] = 0;
}
}
RZMaze::~RZMaze()
{
int i;
for(i = 0; i < n; i++) delete [] maze[i];
delete maze;
for(i = 0; i < n; i++) delete [] bestx[i];
delete bestx;
}
void RZMaze::SaveSol()
{
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++) bestx[i][j] = maze[i]
[j];
}
}
bool RZMaze::InMaze(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y< m;
}
//遞歸回溯函數，dep表示已經走過了多少個方格，(x,y)為當前坐標，di為已經拐彎的次數
void RZMaze::Backtrack(int dep, int x, inty, int di)
{
int i; int p, q; int tmp;
if(dep == m * n - k && x == Juliet[0] && y == Juliet[1])//找到一個解
{
if(dirs < bestc)
{
bestc = dirs; //更新最優值
bccount = 1; //找到第一個最優解
SaveSol(); //更新最優解
}
else if(dirs == bestc)
{
bccount++; //最優解個數加1
}
return;
}
if(dirs > bestc) return; //找不到更好的解 剪枝
else
{
for(i = 0; i < 8; i++) //8個方向逐一試探
{
p = x + dir[i][0]; q = y + dir[i][1]; //計算下一個位置
if(!InMaze(p, q) || maze[p][q] != 0) //不在迷宮內或者以前來過或者封閉房間
{
continue;
}
tmp = maze[p][q];
maze[p][q] = dep + 1; //下一個走到的位置
if(dep > 1 && di != i) dirs++; //拐彎(第一次探路不算拐彎)
Backtrack(dep + 1, p, q, i); //遞歸
if(dep > 1 && di != i) dirs--; //撤銷
maze[p][q] = tmp;
}
}
}
void RZMaze::Process()
{
bccount = 0; bestc = n * m; dirs = 0;
maze[Romeo[0]][Romeo[1]] = 1;
Backtrack(1, Romeo[0], Romeo[1], 0);
}
void RZMaze::ReadData(fstream &fileIn)
{
int i; int r, c;
for(i = 0; i < k; i++)
{
fileIn >> r >> c;
maze[r - 1][c - 1] = -1; //把封閉房間標記-1
}
fileIn >> r >> c;
Romeo[0] = r - 1; Romeo[1] = c - 1;
fileIn>>r>>c;
Juliet[0] = r - 1; Juliet[1] = c - 1;
}
void RZMaze::Output(fstream &fileOut)
{
int i, j;
if(bccount == 0)
{
cout << "No Solution\n";
fileOut << "No Solution\n";
return;
}
cout << bestc << '\n' << bccount << '\n';
fileOut << bestc << '\n' << bccount << '\n';
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
cout << bestx[i][j] << '\t';
fileOut << bestx[i][j] << '\t';
}
cout << '\n';
fileOut << '\n';
}
}
int main()
{
int n, m, k;
fstream fileIn, fileOut;
fileIn.open("in.txt", ios::in);
fileOut.open("out.txt", ios::out);
if(!fileIn)
{
cout<<"文件打開錯誤！"<<endl;
return 0;
}
fileIn >> n >> m >> k;
RZMaze r(n, m, k);
r.ReadData(fileIn);
r.Process();
r.Output(fileOut);
return 0;
}
添加回答
舉報
0/150
提交
取消