bfs记忆搜索求助输出有亿点不对
查看原帖
bfs记忆搜索求助输出有亿点不对
447562
像素旋转楼主2021/4/21 11:04
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
struct Coordi {
	int x0;
	int y0;
	Coordi(int a, int b) { this->x0=a, this->y0 = b; }
	Coordi():Coordi(0,0){  }
};
int bfs(int,int);
queue<Coordi> a;
int walk[8][2] = { {2,1},{1,2},{-1,2}
,{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}
};
int visited[400][400]{0};
int step = 0;
int n, m;//棋盘大小
//遍历每个点对每个点都进行一次bfs
int main(void) {
	int x, y;//马的坐标
	cin >> n >> m >> x >> y;
	Coordi temp(x, y);
	a.push(temp);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printf("%-5d",bfs(i,j));
		cout << endl;
	}
	return 0;
}
int bfs(int i,int j) {
	int ans = 0;
	if (visited[i][j] != 0)
		return visited[i][j];
	while (!a.empty()) {
		Coordi temp = a.front();
		a.pop();
		for (int p = 0; p < 8; p++) {
			int x = temp.x0 + walk[p][0];
			int y = temp.y0 + walk[p][1];
			if (x > n || x<1 || y>m || y < 1||visited[x][y]!=0)
				continue;
			Coordi tmp = { x,y };
			ans++;
			visited[x][y] = ans;
			if (x == i && y == j)
				break;
			a.push(tmp);
		}
	}
	if (!a.empty()) {//队列非空
		while (!a.empty())
			a.pop();//清空队列
		return visited[i][j]=ans;
	}
	else
		return -1;
}
2021/4/21 11:04
加载中...