#include <iostream>
#include <fstream>
using namespace std;
struct RZMaze
{
protected:
static int dir[8][2]; //8個(gè)方向
int n, m, k; //行數(shù)、列數(shù)、封閉房間數(shù)
int Romeo[2]; //Romeo所在的位置
int Juliet[2]; //Juliet所在的位置
int **maze; //迷宮數(shù)組
int **bestx; //保存最優(yōu)解
int bestc; //保存最優(yōu)值
int dirs; //當(dāng)前拐彎次數(shù)
int bccount; //最優(yōu)解的個(gè)數(shù)
public:
RZMaze(int nn, int mm, int kk); //構(gòu)造函數(shù) //給所有的方格標(biāo)記
~RZMaze(); //析構(gòu)函數(shù)
bool InMaze(int x, int y); //判斷坐標(biāo)(x,y)是否還在迷宮內(nèi)
void Backtrack(int dep, int x, int y, int di); //遞歸回溯 走過(guò)多少個(gè)字 已經(jīng)拐了多少?gòu)?br/>void ReadData(fstream &fileIn); //從文件中讀入數(shù)據(jù)
//先讀封閉房間的行號(hào)和列號(hào)寫(xiě)入r,c
void SaveSol(); //保存當(dāng)前解為最優(yōu)解
void Process(); //處理函數(shù)
void Output(fstream &fileOut); //將計(jì)算結(jié)果輸出到文件中
};
//初始化8個(gè)方向的偏移量
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;
}
//遞歸回溯函數(shù)，dep表示已經(jīng)走過(guò)了多少個(gè)方格，(x,y)為當(dāng)前坐標(biāo)，di為已經(jīng)拐彎的次數(shù)
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])//找到一個(gè)解
{
if(dirs < bestc)
{
bestc = dirs; //更新最優(yōu)值
bccount = 1; //找到第一個(gè)最優(yōu)解
SaveSol(); //更新最優(yōu)解
}
else if(dirs == bestc)
{
bccount++; //最優(yōu)解個(gè)數(shù)加1
}
return;
}
if(dirs > bestc) return; //找不到更好的解 剪枝
else
{
for(i = 0; i < 8; i++) //8個(gè)方向逐一試探
{
p = x + dir[i][0]; q = y + dir[i][1]; //計(jì)算下一個(gè)位置
if(!InMaze(p, q) || maze[p][q] != 0) //不在迷宮內(nèi)或者以前來(lái)過(guò)或者封閉房間
{
continue;
}
tmp = maze[p][q];
maze[p][q] = dep + 1; //下一個(gè)走到的位置
if(dep > 1 && di != i) dirs++; //拐彎(第一次探路不算拐彎)
Backtrack(dep + 1, p, q, i); //遞歸
if(dep > 1 && di != i) dirs--; //撤銷(xiāo)
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; //把封閉房間標(biāo)記-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<<"文件打開(kāi)錯(cuò)誤！"<<endl;
return 0;
}
fileIn >> n >> m >> k;
RZMaze r(n, m, k);
r.ReadData(fileIn);
r.Process();
r.Output(fileOut);
return 0;
}
