求助,bfs方法。。。
查看原帖
求助,bfs方法。。。
419652
MOXCOOT楼主2021/3/14 21:05

可以认为是全场有九个点不能走。。。

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
typedef pair<int, int> P;
int x, y, m, n;
int sum = 0;
int dx[] = { -2,-2,-1,-1 ,1,1,2,2,0 };            //马儿的位置
int dy[] = { 1,-1 ,2,-2,-2,2,-1,1,0 };
int rdx[] = { 1,0 };                               //卒的走向
int rdy[] = { 0,1 };
P par[9];
int bfs() {
	queue<P> que;
	while (que.size())que.pop();     //将que队列清空,虽然可能有点无关紧要
	que.push(P(0,0));              //起点
	while (que.size()) {
		P p = que.front();  //取出第一个
		que.pop();
		if (p.first == n && p.second == m) {    //如果到达终点就将总方法数+1
			sum++;
			goto stop2;
		}		
		for (int j = 0; j < 1; j++) {            //卒的两种走法
			int rx = p.first + rdx[j];
			int ry = p.second + rdy[j];
			if (rx > n || ry > m) {             //如果走出地图边界就continue
				goto stop1;
			}
			for (int i = 0; i < 9; i++) {        //如果碰上不能走的点就换走法
				if (rx == par[i].first && ry == par[i].second) {
					goto stop1;
				}
			}
			que.push(P(rx, ry));      //没碰上的话就留下
		stop1:;
		}
	stop2:;
	}
	return sum;
}
int main() {
	cin >> n >> m >> x >> y;
	for (int i = 0; i < 9; i++) {         //par[]存的是不能走到的点
		par[i].first= x + dx[i];
		par[i].second= y + dy[i];
	}
	cout << bfs();
}
2021/3/14 21:05
加载中...