P1443 马的遍历

同样是一个bfs水题。。。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> St;

St start;

queue<St> sts;

map<St, int> dist;

int n, m, x, y;

const int dx[] = {-1, 1, 2, 2, 1, -1, -2, -2};

const int dy[] = {2, 2, 1, -1, -2, -2, -1, 1};

//-----------------

void bfs() {

	sts.push(start);

	while(!sts.empty()) {

		St now = sts.front(); sts.pop();

		int nowx = now.first;

		int nowy = now.second;

		for(int i = 0; i < 8; i++) {

			int newx = nowx + dx[i];

			int newy = nowy + dy[i];

			if(newx > 0 && newx <= n && newy > 0 && newy <= m) {

				St neww(newx, newy);

				if(dist.count(neww)) continue;

				dist[neww] = dist[now] + 1;

				sts.push(neww);

			}

		}

	}

}

void output() {

	for(int i = 1; i <= n; i++) {

		for(int j = 1; j <= m; j++) {

			if(i==x&&j==y) printf("%-5d", 0);

			else {

				St now(i, j);

				int d = dist[now];

				if(d) printf("%-5d", d);

				else printf("%-5d", -1);

			}

		}

		cout << endl;

	}

}

//-----------------

int main() {

	cin >> n >> m >> x >> y;

	start.first = x;

	start.second = y;

	bfs();

	output();

	return 0;

}

不过莫名其妙不知道为什么最后一个点没有过

巴特西

P1443 马的遍历

最新文章

热门文章