グリッドグラフ変換 LIB::GridGraph

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

namespace LIB {
	using GG=graph<ll>;
	template<class W, class GG>class GridGraph {
		using ll=long long;
		template<class T>using vve=vector<vector<T>>;
		GG& g;
		vve<ll> ndtable;
	public:
		GridGraph(vve<W>& grid, ll dir, W wall, GG& g):g(g) {
			vector<pair<ll,ll>> d4={{-1,0},{0,-1},{0,1},{1,0}};
			vector<pair<ll,ll>> d8={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
			vector<pair<ll,ll>> dt=(dir==4)?d4:d8;
			ll nd=0;
			ndtable.resize(grid.size(),vector<ll>(grid[0].size(),-1));
			for(ll y=0;y<(ll)grid.size();y++) for(ll x=0;x<(ll)grid[0].size();x++) {
				if(grid[y][x]==wall) continue;
				ndtable[y][x]=nd++;
			}
			g.resize(nd);
			for(ll y=0;y<(ll)grid.size();y++) for(ll x=0;x<(ll)grid[0].size();x++) {
				if(grid[y][x]==wall) continue;
				for(auto&[dy,dx]:dt) {
					if(y+dy<0||(ll)grid.size()<=y+dy||x+dx<0||(ll)grid[0].size()<=x+dx) continue;
					if(grid[y+dy][x+dx]==wall) continue;
					g[ndtable[y][x]].push_back({ndtable[y+dy][x+dx],1});
				}
			}
		}
		ll GetNode(ll y, ll x) { return ndtable[y][x]; }
	};
}

実装例

https://atcoder.jp/contests/atc001/submissions/48519344