猫捉老鼠
一只猫和一只老鼠在一个矩形的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。
猫和老鼠可以进入任意一个空的方格中。但是，无论猫或老鼠都不能进入有障碍的方格。
我们可以用字符组成的二维数组表示迷宫，如下图所示。
*...*.....
......*...
...*...*..
..........
...*.c....
*.....*...
...*......
..m......*
...*.*....
.*.*......
其中
"." : 空方格:
"*" : 障碍
"m" : 老鼠
"c" : 猫
现在,猫想捉到老鼠,它首先去计算如何才能最快走到老鼠的地方.我们帮它计算一下吧.
下面是猫可以走的一个路线, 猫走6步可以到达老鼠的位置, 这里路线用"@"表示.
*...*.....
......*...
...*...*..
..........
...*.c....
*....@*...
...*.@....
..m@@@...*
...*.*....
.*.*......
要求:
. 控制台程序.
. 控制台输入:
. 地图大小(长宽)
. 障碍的出现的几率.
. 猫的位置/老鼠的位置
. 控制台输出:
. 原始的地图(格式参考上面)
. 猫最少要走多步可以到达老鼠的位置.
. 猫走的路径(用地图表示)
/**
**@Author: xuwf
**@Desc: 猫捉老鼠，求最短路径
**/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define BAR_CHAR ('*')
#define CAT_CHAR ('c')
#define MOUSE_CHAR ('m')
#define ROUTE_CHAR ('@')
#define EMPTY_CHAR ('.')
#define CHILD_MAX_NUM (4) //最多子节点数目
typedef struct pos {
int x;
int y;
}pos_t;
/**
**@Name: pos_equal
**@In: pos_t *a
pos_t *b
**@Out:
**@Ret: int, 相同返回0， 否则返回-1
**@Desc: 比较两坐标是否相同
**@Author: xuwf
**@Date: 2012-3-5
**/
int pos_equal(pos_t *a, pos_t *b)
{
if (!a || !b) {
return -1;
}
if (a->x == b->x && a->y == b->y) {
return 0;
}
return -1;
}
/***********************************************************
*node and operate
***********************************************************/
typedef struct node node_t;
struct node {
pos_t pos;
node_t *parent;
node_t *next;
};
node_t *node_new(node_t *parent, pos_t *pos)
{
node_t *node = NULL;
node = (node_t *)calloc(1, sizeof(node_t));
if (!node) {
return NULL;
}
node->parent = parent;
node->pos = *pos;
return node;
}
int node_add(node_t *node, node_t *new_node)
{
if (!node || !new_node) {
return -1;
}
node->next = new_node;
return 0;
}
void node_delete(node_t *node)
{
if (!node) {
return;
}
free(node);
}
/***********************************************************
*map and operate
***********************************************************/
typedef struct map_info{
char **map;
int map_w;
int map_h;
int bar_num;
}map_info_t;
int destructor_map(map_info_t *info);
int contruct_map(map_info_t *info)
{
int i;
pos_t bar_pos;
if (!info) {
return -1;
}
//清空
info->map = NULL;
//申请map空间
info->map = (char **)calloc(info->map_h, sizeof(char *));
if (!info->map) {
goto _err;
}
for (i = 0; i < info->map_h; i++) {
info->map[i] = (char *)calloc(info->map_w, sizeof(char));
if (!info->map[i]) {
printf("malloc error\n");
goto _err;
}
}
//初始化map
for (i = 0; i < info->map_h; i++) {
memset(info->map[i], EMPTY_CHAR, info->map_w);
}
//放置障碍物
srand(unsigned(time(0)));
for (i = 0; i < info->bar_num; i++) {
bar_pos.x = rand()%info->map_w;
bar_pos.y = rand()%info->map_h;
info->map[bar_pos.y][bar_pos.x] = BAR_CHAR;
}
return 0;
_err:
destructor_map(info);
return -1;
}
int destructor_map(map_info_t *info)
{
int i = 0;
if(!info || !info->map) {
return -1;
}
for (i = 0; i < info->map_h; i++) {
if (info->map[i]) {
free(info->map[i]);
}
}
free(info->map);
info->map = NULL;
return 0;
}
void print_map(map_info_t *info)
{
int i,j;
if (!info || !info->map) {
return;
}
printf("map width=%d, height=%d, barriers num=%d\n", info->map_w, info->map_h, info->bar_num);
for (i = 0; i < info->map_h; i++) {
for (j = 0; j < info->map_w; j++) {
printf("%c", info->map[i][j]);
}
printf("\n");
}
}
//检查位置是否合法
int check_pos(map_info_t *info, pos_t *pos)
{
if (!info || !info->map || !pos) {
return -1;
}
//x
if (pos->x < 0 || pos->x >= info->map_w) {
return -1;
}
//y
if (pos->y < 0 || pos->y >= info->map_h) {
return -1;
}
//if there has barrier
if (BAR_CHAR == info->map[pos->x][pos->y]) {
return -1;
}
return 0;
}
//放置猫和鼠
int put_cat_and_mouse(map_info_t *info, pos_t *cat_pos, pos_t *mouse_pos)
{
if (!info || !info->map) {
return -1;
}
if (!cat_pos || !mouse_pos) {
return -1;
}
//check cat pos
if (check_pos(info, cat_pos) < 0) {
printf("cat pos is err\n");
return -1;
}
info->map[cat_pos->x][cat_pos->y] = CAT_CHAR;
//check mouse pos
if (check_pos(info, mouse_pos) < 0) {
printf("mounse pos is err\n");
return -1;
}
info->map[mouse_pos->x][mouse_pos->y] = MOUSE_CHAR;
return 0;
}
//核心算法，采用广度优先遍历，思路：不断将子节点添加到链表后
int find_route(map_info_t *info, pos_t *cat_pos, pos_t *mouse_pos)
{
node_t *cat_node = NULL;
node_t *child_node = NULL;
node_t *p = NULL;
node_t *tail = NULL;
pos_t child_pos;
static int dir_array[4][2] = {
{0, -1},//上
{-1, 0},//左
{0, 1},//下
{1, 0}};//右
int i = 0;
cat_node = node_new(NULL, cat_pos);
tail = p = cat_node;
while (p) {
for (i = 0; i < 4; i++) {
child_pos.x = p->pos.x + dir_array[i][0];
child_pos.y = p->pos.y + dir_array[i][1];
if (check_pos(info, &child_pos) < 0) {
continue;
}
if (p->parent && (0 == pos_equal(&child_pos, &p->parent->pos))) {//父节点除外
continue;
}
//add node
child_node = node_new(p, &child_pos);
if (!child_node) {
printf("new node fail\n");
return -1;
}
node_add(tail, child_node);
tail = child_node;
if (0 == pos_equal(&child_pos, mouse_pos)) {
goto _found;
}
}
p = p->next;
}
printf("can't find route\n");
goto _free;
_found:
//print route
while (p->parent) {
info->map[p->pos.x][p->pos.y] = ROUTE_CHAR;
p = p->parent;
}
_free:
p = cat_node;
while (p) {
child_node = p->next;
node_delete(p);
p = child_node;
}
return 0;
}
int main(int argc, char *argv[])
{
map_info_t info;
float bar_pro = 0;//概率
pos_t cat_pos, mouse_pos;
//memset
memset(&info, 0, sizeof(info));
printf("please input map width and height:");
scanf("%d %d", &info.map_w, &info.map_h);
printf("plese input the probability of barriers:");
scanf("%f", &bar_pro);
if (bar_pro >= 1) {
printf("probability of barriers must less then 1\n");
return -1;
}
info.bar_num = (info.map_w*info.map_h)*bar_pro;
//contruct map
contruct_map(&info);
print_map(&info);
while (1) {
printf("please input cat and mouse pos:\n");
scanf("%d %d %d %d", &cat_pos.x, &cat_pos.y, &mouse_pos.x, &mouse_pos.y);
if (put_cat_and_mouse(&info, &cat_pos, &mouse_pos) < 0) {
continue;
}
print_map(&info);
printf("find route ...\n");
find_route(&info, &cat_pos, &mouse_pos);
print_map(&info);
}
destructor_map(&info);
return 0;
}