给定一迷宫以及入口和出口的坐标，要求寻找从入口到出口的最短距离。
Input
第一行两个数m和n表示迷宫的行数和列数。迷宫大小不超过45×45。
接下来是m行n列的数，用来表示迷宫，1表示墙，0表示通路。
第二行四个数x1,y1,x2,y2分别表示起点和终点的坐标。
Output
从起点到终点所经过的最短路径长度，如果不存在，输出"no path!"
Sample Input
8 8
0 0 0 0 0 0 0 1
0 1 1 1 1 0 0 0
0 1 0 1 1 1 1 0
0 1 1 0 0 0 0 0
0 0 0 1 0 1 1 1
0 1 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 1 7
Sample Output
8
用队列求解。
不同于网上找到的答案的，运用c语言的知识。
不同于网上找到的答案的
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct data
{
int x;
int y;
int len;
} QDataType; //数据类型
typedef struct ListNode //通过链表实现的
{
QDataType _data;
struct ListNode *_pNext;
} ListNode, *pListNode;
typedef struct Queue
{
pListNode _pHead; //头指针
pListNode _pTail; //尾指针
} Queue;
pListNode BuyNode(QDataType d)
{
pListNode new = malloc(sizeof(ListNode));
new->_data = d;
new->_pNext = NULL;
return new;
}
void QueueInit(Queue *q)
{
assert(q);
QDataType d;
q->_pHead = BuyNode(d);
q->_pTail = q->_pHead;
}
void QueuePush(Queue *q, QDataType d)
{
assert(q);
q->_pTail->_pNext = BuyNode(d);
q->_pTail = q->_pTail->_pNext;
}
void QueuePop(Queue *q)
{
pListNode dNode = q->_pHead->_pNext;
if (dNode)
{
q->_pHead->_pNext = dNode->_pNext;
if (q->_pHead->_pNext == NULL)
{
q->_pTail = q->_pHead;
} //如果只有一个元素，删完后ptail会悬空
free(dNode);
}
}
int QueueSize(Queue *q)
{
assert(q);
pListNode pre = q->_pHead->_pNext;
int count = 0;
while (pre)
{
count++;
pre = pre->_pNext;
}
return count;
}
int QueueEmpty(Queue *q)
{
return NULL == q->_pHead->_pNext;
}
QDataType Front(Queue *q)
{
return q->_pHead->_pNext->_data;
}
QDataType Back(Queue *q)
{
return q->_pTail->_data;
}
Queue *q;
int ds[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m, n;
int a[100][100];
int bfs(int x, int y, int x2, int y2)
{
QDataType d = {x, y, 0};
QueuePush(q, d);
a[x][y] = 2;
while (!QueueEmpty(q))
{
d = Front(q);
QueuePop(q);
for (int i = 0; i < 4; i++)
{
int tx = d.x + ds[i][0];
int ty = d.y + ds[i][1];
if (tx == x2 && ty == y2)
{
return d.len+1;
}
if (tx >= 0 && tx < m && ty >= 0 && ty < n && a[tx][ty] == 0)
{
QDataType t = {tx, ty, d.len+1};
QueuePush(q, t);
a[tx][ty] = 2;
}
}
}
return 0;
}
int main()
{
int x1, y1, x2, y2;
int i, j;
q = (Queue *)malloc(sizeof(Queue));
QueueInit(q);
scanf("%d %d", &m, &n);
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
}
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int len = bfs(x1, y1, x2, y2);
if (len>0)
{
printf("%d", len);
}
else
{
printf("no path!");
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int findMinRoad(int road[100][100],int x0, int y0,int x1,int y1);
int main()
{
int row,col;
int x0,y0,x1,y1;
int road[100][100];
cin>>row>>col;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
cin>>road[i][j];
cin>>x0>>y0>>x1>>y1;
int ans;
ans = findMinRoad(road,x0, y0,x1,y1);
if(ans == -1)
cout<<"no path!";
else
cout<<ans;
return 0;
}
// 利用动态规划求解
int findMinRoad(int road[100][100],int x0, int y0,int x1,int y1){
// 辅助一维数组
int path[y1-y0+1];
int MAX = 99999;
// 初始化
path[0] = road[x0][y0] == 1 ? MAX : 0;
for (int i = y0+1; i <= y1; i++)
path[i-y0] = road[x0][i] == 1 ? MAX : path[i-y0-1]+1;
// 到达各位置的最短路径
for (int i = x0+1; i <= x1; i++)
{
if (road[i][y0] == 0)
{
path[0] += 1;
}else
{
path[0] = MAX;
}
for (int j = y0+1; j <=y1 ; j++)
{
if (road[i][j] == 0)//有路
{
// 到达当前位置的最短路径 =
// min(到达左边一个位置的最短路径+1，到达上面一个位置的最短路径+1)
path[j-y0] = min(path[j-y0-1]+1,path[j-y0]+1);
}else// 墙
{
path[j-y0] = MAX;//无法到达该位置
}
}
}
return path[y1-y0] >= MAX ? -1 : path[y1-y0];
}
这个很简单