下图是一个 n x m 的网格，你需要从你所在的位置拿到任意一本秘籍才能过关。并且只能上下左右四个方向移动，移动一个格子就算一步。
第一行有两个整数 n，m。地图是 n 行 m 列。接下来的 n 行，每行 m 个字符，其中 '.' 代表道路，'#' 代表墙，'S' 代表你所在的位置，'T' 代表通关的位置，'P'代表秘籍的位置。除了墙以外，别的地方都可以通过。你需要找到一条最快通关的路径，即移动的步数最少。并且输出结果到屏幕。其中，1<=n<=15, 3<=m<=15

给一种思路，只求S到T的最短距离

#include <stdio.h>
#include <stdlib.h>

int count = 0;
int t = 999999;

void search(char str[][11], int x, int y)
{
    if (str[x][y] == 'T')
    {
        t = t < count ? t : count;
        return;
    }

    str[x][y] = '#';
    count++;
    if (str[x - 1][y] == '.' || str[x - 1][y] == 'T' )  search(str, x - 1, y);
    if (str[x + 1][y] == '.' || str[x + 1][y] == 'T')   search(str, x + 1, y);
    if (str[x][y - 1] == '.' || str[x][y - 1] == 'T')   search(str, x, y - 1);
    if (str[x][y + 1] == '.' || str[x][y + 1] == 'T')   search(str, x, y + 1);
    
    count--;
    str[x][y] = '.';
    
}
void main()
{
    int i = 0;
    char str[8][11] = {
        { "..####.#.#" },
        { "..#..#...#" },
        { "..#T##.#.#" },
        { ".........." },
        { "..##.#####" },
        { ".........." },
        { "#####...##" },
        { "###....S##" }
    };

    search(str, 7, 7);
    
    printf("%d", t);
    system("pause");
    return;
}

谢谢

广搜啊~这个题应该是用来卡一般广搜的~涉及到重复搜索问题~

其实转化一下就很简单了~第一次先广搜起点到所有秘笈的位置~

第二次广搜终点到所有秘笈的位置~

取两次加起来的最小值~

由于两次搜索除了起点位置不同其余的都一样的~所以广搜函数调用更改起点坐标就可以啦~这样代码利用率挺高的~

化简后实质还是广搜~

P同一个秘籍，不一定到起点和终点的距离都是最短了

为何运行直接输出9

秘籍到起点和终点加起来的距离和最短嘛~

为何不用输入了，直接输出9。。。

把二楼的代码改进了一下~
感觉学多一点优化代码的能力就提升了一点~

#include <stdio.h>
#include <stdlib.h>

#define SEARCH(str,x,y)  str##[x][y]=='.'||str##[x][y]=='T'

int count = 0;
int t = 999999;

void search(char str[][11], int x, int y)
{
    if (str[x][y] == 'T')
    {
        t = t < count ? t : count;
        return;
    }

    str[x][y] = '#';
    count++;

    if (SEARCH(str,x-1,y))
        search(str, x-1, y);

    if (SEARCH(str,x+1,y))
        search(str, x+1, y);

    if (SEARCH(str,x,y-1))
        search(str,x,y-1);

    if (SEARCH(str,x,y+1))
        search(str,x,y+1);
    
    count--;
    str[x][y] = '.';
    
}
void main()
{
    int i = 0;
    char str[8][11] = {
        { "..####.#.#" },
        { "..#..#...#" },
        { "..#T##.#.#" },
        { ".........." },
        { "..##.#####" },
        { ".........." },
        { "#####...##" },
        { "###....S##" }
    };

    search(str, 7, 7);
    
    printf("%d\n", t);
    system("pause");
    return;
}

[此贴子已经被作者于2017-10-4 11:23编辑过]

谢谢， 学习了！