Submission #1131280

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;


struct edge
{
	int to;
	long long cost;
	edge(int to_, long long cost_) :
		to(to_), cost(cost_) {}
};
const long long INF = 123456789012345;
using P = pair<long long, int>;//first:cost,second:vertice
void dijkstra(vector<edge>graph_[], long long dist[], int n_, int s_)
{
	priority_queue<P, vector<P>, greater<P>>que;
	que.push({ 0,s_ });
	fill(dist, dist + n_, INF);
	dist[s_] = 0ll;
	while (!que.empty())
	{
		auto q = que.top();
		que.pop();
		long long thd = q.first;
		int thv = q.second;
		if (thd > dist[thv])
		{
			continue;
		}
		for (auto ed : graph_[thv])
		{
			if (dist[ed.to] > ed.cost + thd)
			{
				dist[ed.to] = ed.cost + thd;
				que.push({ dist[ed.to],ed.to });
			}
		}
	}
}

vector<edge>graph[512];
long long dist[512];

int main(void)
{
	int n;
	cin >> n;
	int ss = 512;
	if (n == 2)ss = 16;
	int ms = n * n;
	for (int board = 0; board < ss; ++board)
	{
		bool s[9] = {};
		for (int i = 0; i < ms; ++i)
		{
			if (board & (1 << i))s[i] = true;
		}
		for (int m = 0; m < ms; ++m)
		{
			bool t[9];
			for (int i = 0; i < ms; ++i)t[i] = s[i];
			int p = m / n;
			int q = m % n;
			int kio[3];
			for (int i = 0; i < n; ++i)kio[i] = s[p * n + i];
			for (int i = 0; i < n; ++i)t[i * n + q] = kio[i];
			int to = 0;
			for (int i = 0; i < ms; ++i)
			{
				to += t[i] ? (1 << i) : 0;
			}
			graph[to].emplace_back(board, 1);
		}
	}
	int id = 0;
	int inp[9];
	for (int i = 0; i < ms; ++i)
	{
		char ch;
		cin >> ch;
		inp[i] = (ch == '.');
	}
	for (int i = 0; i < ms; ++i)
	{
		id += inp[i] ? (1 << i) : 0;
	}
	dijkstra(graph, dist, ss, 0);
	cout << ((dist[id] == INF) ? -1 : dist[id]) << endl;
	return 0;
}

Submission Info

Judge Result