求數據結構的迷宮問題和農夫過河問題 和一元稀疏矩陣的加減法問題 急
正好我今天也是那個課設
農夫過河
#include
#include
using namespace std;
#define VertexNum 16 //最大頂點數
typedef struct // 圖的頂點
{
int farmer; // 農夫
int wolf; // 狼
int sheep; // 羊
int veget; // 白菜
}Vertex;
typedef struct
{
int vertexNum; // 圖的當前頂點數
Vertex vertex[VertexNum]; // 頂點向量（代表頂點）
bool Edge[VertexNum][VertexNum]; // 鄰接矩陣. 用於存儲圖中的邊，其矩陣元素個數取決於頂點個數，與邊數無關
}AdjGraph; // 定義圖的鄰接矩陣存儲結構
bool visited[VertexNum] = {false}; // 對已訪問的頂點進行標記（圖的遍歷）
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路徑，即與某頂點到下一頂點的路徑
// 查找頂點（F，W，S，V）在頂點向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf , int sheep, int veget)
{
// 從0開始查找
for (int i = 0; i < graph->vertexNum; i++)
{
if ( graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf
&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget )
{
return i; //返回當前位置
}
}
return -1; //沒有找到此頂點
}
// 判斷目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//當農夫與羊不在一起時，狼與羊或羊與白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true; // 安全返回true
}
}
// 判斷狀態i與狀態j之間是否可轉換
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三個條件不同時滿足兩個且農夫狀態改變時，返回真, 也即農夫每次只能帶一件東西過橋
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 創建連接圖
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的圖的頂點
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 鄰接矩陣初始化即建立鄰接矩陣
graph->vertexNum = i;
for (i = 0; i < graph->vertexNum; i++)
{
for (j = 0; j < graph->vertexNum; j++)
{
// 狀態i與狀態j之間可轉化，初始化為1，否則為0
if (isConnect(graph, i, j))
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判斷在河的那一邊
string judgement(int state)
{
return (0 == state) ? "左岸" : "右岸" ;
}
// 輸出從u到v的簡單路徑，即頂點序列中不重復出現的路徑
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;
cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;
while (i != end)
{
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
i = retPath[i];
}
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
}
// 深度優先搜索從u到v的簡單路徑 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //標記已訪問過的頂點
if (start == end)
{
return ;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);
if (visited[end]) // 有結果
{
printPath(&graph, start, end);
return 0;
}
return -1;
}
