首页 > 代码库 > 全是套路——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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。