Submission #2554810

---

Source Code Expand

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
	arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) {
		fill_all(i, v);
	}
}

int32_t H=19,W=15;
char map[30][30];
int mapint[30][30];
int32_t start_h, start_w = 0;
std::vector<std::pair<int, int>> pos;
std::map<std::pair<int, int>, int> pos_map;
int postable[21*8];

const int diffh[8] = {0,0,1,1,1,-1,-1,-1};
const int diffw[8] = {-1,1,-1,0,1,-1,0,1};

const int32_t INF = 100000;
int32_t dp[21 * 8][1 << 20];
int32_t func(int i, std::bitset<20> mask, std::pair<int,int> posi)
{
	if (posi.first >= H) {
		return 0;
	}
	auto& memo = dp[postable[i]][mask.to_ulong()];

	if (memo != -1) { return memo; }
	if (posi.second < 0 || posi.second >= W) {
		return INF;
	}

	int32_t res = INF;
	for (size_t cc = 0; cc < 8; cc++)
	{
		int last_index = 0;
		std::bitset<20> nextmask = mask;
		bool ok = false;
		auto t = posi;
		t.first += diffh[cc];
		t.second += diffw[cc];
		if (t.first < 0 || t.first >= H) { continue; }
		if (t.second < 0 || t.second >= W) { continue; }
		while (map[t.first][t.second] == 'X' && mask[mapint[t.first][t.second]] == true)
		{
			ok = true;
			last_index = mapint[t.first][t.second];
			nextmask[mapint[t.first][t.second]] = false;


			t.first += diffh[cc];
			t.second += diffw[cc];
			if (t.first < 0) { ok = false; break; }
			if (t.first >= H) { break; }
			if (t.second < 0 || t.second >= W) { ok = false; break; }
		}

		if (ok) {
			res = std::min(res, func(last_index * 8 + cc, nextmask, t)+1);
		}
	}
	return memo = res;
}

int main()
{
	fill_all(dp, -1);
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	for (size_t i = 0; i < H; i++)
	{
		in >> map[i];
	}

	for (size_t i = 0; i < H; i++)
	{
		for (size_t j = 0; j < W; j++)
		{
			if (map[i][j]=='O')
			{
				start_h = i;
				start_w = j;
			}
			if (map[i][j] == 'X')
			{
				pos.emplace_back(i, j);
				mapint[i][j] = pos.size() - 1;
				auto v = pos.back();
				for (size_t cc = 0; cc < 8; cc++)
				{
					auto t = v;
					t.first += diffh[i];
					t.second += diffw[i];
					pos_map[t] = 0;
				}
			}
		}
	}

	{
		int count = 0;
		for (auto& i : pos_map)
		{
			i.second = count++;
		}
	}

	for (int i = 0;i<pos.size();++i)
	{
		for (size_t cc = 0; cc < 8; cc++)
		{
			auto t = pos[i];
			t.first += diffh[cc];
			t.second += diffw[cc];
			postable[i * 8 + cc] = pos_map[t];
		}
	}
	postable[(pos.size()) * 8] = (pos.size()) * 8;
	auto v = func((pos.size()) * 8, std::bitset<20>((1 << 20) - 1), { start_h, start_w });
	if (v == INF) {
		out << -1 << endl;
	}
	else {
		out << v << endl;
	}


	return 0;
}
#endif

Submission Info

Judge Result