int main() {
	queue< vector<vector<int>>> q;
	map<vector<vector<int>>, int> mp;
	int was[n][n];
	int px, py;
	int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

	vector<vector<int> > t = { {2, 1, 3}, {4, 6, 5}, {7, 8, 0} };
	vector<vector<int> > otvet = { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} };
	q.push(t);
	mp[t] = 1;

	while (!q.empty()) {
		auto k = q.front();
		int pos = mp[k];
		if (k == otvet) {
			cout << pos;
			getchar();
			return 0;
			getchar();
		}
		q.pop();
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (k[i][j] == 0) {
					px = i;
					py = j;
				}
			}
		}
		for (int d = 0; d < 4; d++) {
			if (((px + dx[d]) < 3) && ((px + dx[d]) >= 0) && ((py + dy[d]) < 3) && ((py + dy[d]) >= 0)) {

				int l = k[px][py];
				k[px][py] = k[px + dx[d]][py + dy[d]];
				k[px + dx[d]][py + dy[d]] = l;


				if (!mp[k]) {
					mp[k] = pos + 1;
					q.push(k);
				}


			}
		}



	}

	getchar();

}