BOJ 7562:夜の移動

✔問題リンク

BOJ 7562：夜の移動

✔トラブルシューティングポリシー

グラフィックナビゲーション

BFS(Breadth First Search)

✔解決過程

BFSを誠実にやればいい.通常2次元のBFSは上下左右にナビゲートされるが,この問題は8方向にナビゲートするだけでよい.

✔正解コード

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int map[300][300];
	int dx[8] = {1,2,2,1,-1,-2,-2,-1};
	int dy[8] = {2,1,-1,-2,-2,-1,1,2};
	
 	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, l, startX, startY, endX, endY;
	cin >> n;
	queue<pair<int,int>> q;
	
	while(n--) {
		cin >> l;
		cin >> startX >> startY;
		cin >> endX >> endY;
		
		fill(&map[0][0], &map[299][300],-1);
		
  		map[startY][startX] = 0;
		pair<int,int> st = {startY, startX};
  		q.push(st);
  		while(!q.empty()) {
			pair<int,int> cur = q.front();
			q.pop();
			for(int i=0;i<8;i++) {
				int newY = cur.first + dy[i];
				int newX = cur.second + dx[i];
	  			if(newX<0 || newY<0 || newX>=l || newY>=l) continue;
	 	 		if(map[newY][newX] != -1) continue;
	  			map[newY][newX] = map[cur.first][cur.second] + 1;
	  			q.push({newY, newX});
			}
  		}
		cout << map[endY][endX] << '\n';
  	}
}

✔ Check Point

PSは通常グローバル配列であり、ここではfill関数を使用するためにローカルに配置される.2 D配列をfill関数に初期化する場合は、[0,0]から開始し、rowをMAX-1、columをMAXに終了します.コード再構築は次の機会です...