Submission #358671

---

Source Code Expand

#include<iostream>
#include<fstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>

#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>

#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);

#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define LL long long
typedef complex<double> dc;
const LL INF = 1 << 30;
const double eps = 1e-8;
int H, W;
int dir[4][2] = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

void bfs(map<vector<int>, int> &used, int s, vector<int> c){
	int d = 0,h,w,new_h,new_w,new_s;
	queue<pair<vector<int>, int>> q;
	q.push(make_pair(c, s));
	used[c] = d;

	while (q.empty() == false){
		c = q.front().first;
		s = q.front().second;
		d = used[c];
		q.pop();
		h = s / W; w = s%W;
		if (d < 12){
			rT(i, 4){
				new_h = h + dir[i][0];
				new_w = w + dir[i][1];
				new_s = new_h*W + new_w;
				if (0 <= new_h&&new_h < H && 0 <= new_w&&new_w < W){
					swap(c[s], c[new_s]);
					if (used.count(c) == 0){
						used[c] = d + 1;
						q.push(make_pair(c, new_s));
					}
					swap(c[s], c[new_s]);
				}
			}
		}
	}

}
void print(vector<int> x){
	rT(i, H){
		rT(j, W)printf("%2d ", x[i*W + j]);
		cout << endl;
	}
}
int main(void){
	map<vector<int>, int>st;
	map<vector<int>, int>ed;
	vector<int> is, ans;
	int start,res=24;
	cin >> H >> W;
	is.resize(H*W);
	ans.resize(H*W);
	rT(i, H*W){ cin >> is[i]; if (!is[i])start = i; ans[i] = (i + 1) % (H*W); }
	bfs(st, start, is);
	bfs(ed, H*W - 1, ans);
	itr(i, st){
	//	print(i->first);
		if (ed.count(i->first)){
			res = min(res, i->second + ed[i->first]);
		}
	}
	cout << res << endl;

	return(0);
}

Submission Info

Judge Result