首页 > 代码库 > 全是套路——BFS

全是套路——BFS

#include <iostream>#include <vector>#include <string>#include <vector>#include <algorithm>#include <stack>#include <math.h>#include <limits.h>#include <set>#include <memory>#include <queue>using namespace std;struct point{    int x;    int y;    point *parent;    int step;};int map[9][9] = {         1, 1, 1, 1, 1, 1, 1, 1, 1,                         1, 0, 0, 1, 0, 0, 1, 0, 1,                         1, 0, 1, 1, 1, 0, 0, 0, 1,                         1, 0, 1, 0, 0, 0, 0, 1, 1,                         1, 0, 1, 0, 1, 1, 0, 0, 1,                         1, 0, 1, 0, 1, 1, 0, 0, 1,                         1, 0, 0, 0, 1, 1, 0, 0, 1,                         1, 1, 0, 1, 1, 0, 0, 0, 1,                         1, 1, 1, 1, 1, 1, 1, 1, 1, };vector<point> p;int BFS(point s,point e){    queue<point> q;    q.push(s);    while (!q.empty())    {        point start = q.front();        point *s1 = new point; s1->x = start.x; s1->y = start.y; s1->parent = start.parent;        q.pop();        if (start.x == e.x&&start.y == e.y)        {            p.push_back(start);            return start.step;        }        if (map[start.x + 1][start.y] != 1 && start.x + 1 <= 8 && start.x + 1 >= 0)        {            point tmp = { start.x + 1, start.y, s1, start.step + 1 };            map[start.x + 1][start.y] = 1;            q.push(tmp);        }        if (map[start.x - 1][start.y] != 1 && start.x - 1 <= 8 && start.x - 1 >= 0)        {            point tmp = { start.x - 1, start.y, s1, start.step + 1 };            map[start.x - 1][start.y] = 1;            q.push(tmp);        }        if (map[start.x][start.y + 1] != 1 && start.y + 1 <= 8 && start.y + 1 >= 0)        {            point tmp = { start.x, start.y + 1, s1, start.step + 1 };            map[start.x][start.y + 1] = 1;            q.push(tmp);        }        if (map[start.x][start.y - 1] != 1 && start.y - 1 <= 8 && start.y - 1 >= 0)        {            point tmp = { start.x, start.y - 1, s1, start.step + 1 };            map[start.x][start.y - 1] = 1;            q.push(tmp);        }        start.step++;    }}int main(){    point s = { 1, 1 }, e = { 7, 7 };    BFS(s, e);    char p1[15] = "abcd", *p2 = "ABCD", str[50] = "xyz";    strcpy(str + 2, strcat(p1 + 2, p2 + 1));    printf("%s", str);    point *point = &p[0];    while (point->parent != NULL)    {        cout << point->x << " " << point->y << endl;        point = point->parent;    }    return 0;}

 

全是套路——BFS