/*
  BFS搜索，A*优化

  八数码问题无解当且仅当
	  展开以后，逆序对的数量是奇数

  估价函数：1~8每个数和最终位置的曼哈顿距离之和

 */
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
typedef pair <int, string> PIS;
char ch;
string start, s;

// 计算估价函数
int f (string state) {
	int ans = 0;
	for (int i = 0; i < 9; i++) {
		if (state[i] == '0') continue;
		int t = state[i] - '1';
		ans += abs (i / 3 - t / 3) + abs (i % 3 - t % 3);
	}
	return ans;
}
int Astar () {
	string end = "123804765";
	unordered_map <string, int> dist;  // 记录当前距离
	priority_queue <PIS, vector <PIS>, greater <PIS>> heap;
	dist[start] = 0;
	heap.push ({f (start), start});
	while (!heap.empty ()) {

		auto t = heap.top ();
		heap.pop ();
		string state = t.second;
		if (state == end) break;  // 提前退出
		int x, y;
		for (int i = 0; i < 9; i++) { // 找到空格
			if (state[i] == '0') {
				x = i / 3, y = i % 3;
				break;
			}
		}

		string source = state;  // 保留原字符串
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i], b = y + dy[i];
			if (a < 0 || a > 2 || b < 0 || b > 2) continue;
			swap (state[a * 3 + b], state[x * 3 + y]);
			if (!dist.count (state) || dist[state] > dist[source] + 1) {
				dist[state] = dist[source] + 1;
				heap.push ({dist[state] + f(state), state});
			}
			state = source;  // 还原原来的字符串
		}
	}
	return dist[end];
}
int main () {
	for (int i = 0; i < 9; i++) {
		cin >> ch;
		start += ch;
		if (ch != '0') s += ch;
	}
	cout << Astar () << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N  = 888;
int n, m, T, ans;
char a[N][N];
pair<int, int > boy, girl, gui[3];

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

int st[N][N] ; // st[i][j] =1 ,代表男孩到过， =2， 代表女孩到过

bool check(int x, int y, int step) {
	if (x < 1 || x > n || y < 1 || y > m)
		return 0;
	if (a[x][y] == 'X')
		return 0;
	// 判断有没有鬼
	for (int i = 1; i <= 2; i++) { // 判断曼哈顿距离
		if (abs(gui[i].first - x) + abs(gui[i].second - y) <= step * 2)
			return 0;
	}
	return 1;
}



// 双向BFS
bool bfs() {
	memset(st, 0, sizeof st);
	queue<pair<int, int > >q1, q2; // 两个队列
	q1.push(boy), q2.push(girl);
	int step = 0;
	while (q1.size() || q2.size()) {
		step++;
		// 男生
		for (int i = 1; i <= 3; i++) {
			for (int j = 0, len = q1.size() ; j < len; j++) {
				auto t  = q1.front();
				q1.pop();
				for (int k = 0; k < 4; k++) {
					int nx = t.first + dx[k], ny = t.second + dy[k];
					if (check(nx, ny, step) == 0)
						continue;
					if (st[nx][ny] == 2) {
						ans = step;
						return 1;
					}
					if (!st[nx][ny]) {
						st[nx][ny] = 1;
						q1.push({nx, ny});
					}
				}
			}
		}
		// 女生
		for (int i = 1; i <= 1; i++) {
			for (int j = 0, len = q2.size() ; j < len; j++) {
				auto t  = q2.front();
				q2.pop();
				for (int k = 0; k < 4; k++) {
					int nx = t.first + dx[k], ny = t.second + dy[k];
					if (check(nx, ny, step) == 0)
						continue;
					if (st[nx][ny] == 1) {
						ans = step;
						return 1;
					}
					if (!st[nx][ny]) {
						st[nx][ny] = 2;
						q2.push({nx, ny});
					}
				}
			}
		}
	}
	return 0;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n >> m;
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
				if (a[i][j] == 'M')
					boy.first = i, boy.second = j;
				if (a[i][j] == 'G')
					girl.first = i, girl.second = j;
				if (a[i][j] == 'Z')
					gui[++cnt].first = i, gui[cnt].second = j;
			}
		if (bfs())
			cout << ans << endl;
		else
			cout << -1 << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 20;

struct node {
	int x, y, hp;
};
int a[N][N], n, m;
int dis[N][N][7];
int sx, sy;

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

void bfs() {
	queue<node> q;
	memset(dis, 0x3f, sizeof dis);
	dis[sx][sy][6] = 0;
	q.push({sx, sy, 6});
	while (q.size()) {
		auto t  = q.top();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			if (t.hp == 1)
				continue;
			int hp = t.hp - 1;
			if (a[nx][ny] == 0)
				continue;
			if (a[nx][ny] == 4)
				hp = 6;
			if (dis[nx][ny][hp] > dis[t.x][t.y][t.hp] + 1) {
				dis[nx][ny][hp] = dis[t.x][t.y][t.hp] + 1;
				q.push({nx, ny, hp});
			}
		}
	}
}



// (x,y) 时间，血量
// dis[x][y][hp] =


// 1 1 1 2 2 2  queue
// 0 1 0 1 0 1 deque
// 1 2 4 2 1 0 3  priority_queue

// deque
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
char a[N][N];

int dx[] = {-1, -1, 1, 1};

int dy[] = {-1, 1, 1, -1};

int ix[] = {-1, -1, 0, 0};

int iy[] = {-1, 0, 0, -1};
char s[] = "\\/\\/";
int dis[N][N];

int n, m;

void bfs() {
	memset(dis, 0x3f, sizeof dis);
	dis[1][1] = 0;
	deque<pair<int, int> >q;
	q.push_front({1, 1});
	while (q.size()) {
		auto t = q.front();
		q.pop_front();
		int x  = t.first, y = t.second;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1)
				continue;
			int ii = x + ix[i], jj = y + iy[i];
			int w = 0;
			if (a[ii][jj] == s[i])
				w = 0;
			else
				w = 1;
			if (dis[nx][ny] > dis[x][y] + w) {
				dis[nx][ny] = dis[x][y] + w;
				if (w)
					q.push_back({nx, ny});
				else
					q.push_front({nx, ny});
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	bfs();
	if (dis[n + 1][m + 1] == 0x3f3f3f3f)
		cout << "NO SOLUTION";
	else
		cout << dis[n + 1][m + 1];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 510;

struct node {
	int x, y;
	int lie; // 0 站 1 横  2 竖
};
node start, end1;

int d[3][4][3] = {
	{{-2, 0, 2}, {0, 1, 1}, {1, 0, 2}, {0, -2, 1}},
	{{-1, 0, 1}, {0, 2, 0}, {1, 0, 1}, {0, -1, 0}},
	{{-1, 0, 0}, {0, 1, 2}, {2, 0, 0}, {0, -1, 2}}
};

int dis[N][N][3];
char a[N][N];
int n, m;
int bfs(node start, node end1) {
	memset(dis, -1, sizeof dis);
	dis[start.x][start.y][start.lie] = 0;
	queue<node>q;
	q.push(start);
	while (q.size()) {
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = t.x + d[t.lie][i][0];
			int ny = t.y + d[t.lie][i][1];
			int nl = d[t.lie][i][2];
			// 1. 越界
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			// 2. 不能走
			if (a[nx][ny] == '#')
				continue;
			if (nl == 0 && a[nx][ny] == 'E')
				continue;
			if (nl == 1 && (ny + 1 > m || a[nx][ny + 1] == '#' ))
				continue;
			if (nl == 2 && (nx + 1 > n || a[nx + 1][ny] == '#' ))
				continue;
			if (dis[nx][ny][nl] == -1) {
				dis[nx][ny][nl] = dis[t.x][t.y][t.lie] + 1;
				q.push({nx, ny, nl});
			}
		}
	}
	return dis[end1.x][end1.y][end1.lie];
}

int main() {
	while (cin >> n >> m, n && m) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
				if (a[i][j] == 'O') {
					end1.x = i, end1.y = j, end1.lie = 0;
				}
			}
		// 找一下起始点
		bool flg = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == 'X') {
					start.x = i, start.y = j, start.lie = 0;
					if (a[i][j + 1] == 'X')
						start.lie = 1;
					if (a[i + 1][j] == 'X')
						start.lie = 2;
					flg = 1;
					break;
				}
			}
			if (flg)
				break;
		}
		int ans = bfs(start, end1);
		if (ans == -1)
			puts("Impossible");
		else
			cout << ans << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int n, k; // k = n/2
long long w;
long long a[N], ans;
vector<long long> weight;

// u 当前搜索的物品，sum 物品和
// 搜 1 - n/2
void dfs1(int u, long long sum) {
	if (u > k) {
		weight.push_back(sum);
		return ;
	}
	dfs1(u + 1, sum); // 当前物品不放进来
	if (sum + a[u] <= w)
		dfs1(u + 1, sum + a[u]); // 当前物品放进来
}

// n/2+1, n
void dfs2(int  u, long long sum) {
	if (u > n) {
		// 和之前搜索出来的 结果匹配
		long long  t = w - sum; // 要匹配的值
		auto tmp = upper_bound(weight.begin(), weight.end(), t) - weight.begin() - 1;
		if (tmp == -1)
			return ;
		else {
			ans = max(ans, weight[tmp] + sum);
			return ;
		}
	}
	dfs2(u + 1, sum);
	if (sum + a[u] <= w)
		dfs2(u + 1, sum + a[u]);
}

int main() {
	cin >> w >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	k  = n / 2;
	dfs1(1, 0);
	sort(weight.begin(), weight.end());
	dfs2(k + 1, 0);
	cout << ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, path[N]; // path  记录路径

// now 当前放置的数字的位置
// depth 能搜索的最大深度
bool dfs(int now, int depth) {
	// path[0] =1 , path[now-1] == n
	if (now == depth)
		return path[now - 1] == n;
	// 判重
	bool st[110] = {0};
	// 放 now 这个位置
	// path[i] + path[j] = path[now]
	for (int i = now - 1 ; i >= 0 ; i--) {
		for (int j = i; j >= 0; j--) {
			int s = path[i] + path[j];
			if (st[s])
				continue;
			if (s > path[now - 1] && s <= n) {
				path[now] = s;
				st[s] = 1;
				if (dfs(now + 1, depth))
					return 1;
			}
		}
	}
	return 0;
}

int main() {
	while (cin >> n, n) {
		int depth = 1;
		path[0] = 1;
		while (!dfs(1, depth))
			depth++;
		for (int i = 0; i < depth; i++)
			cout << path[i] << " ";
		cout << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N], w;
int c[N], ans = 1e9;

// now 当前小猫的编号， cnt 缆车数量
void dfs(int now, int cnt) {
	// 最优性减枝
	if (cnt >= ans)
		return ;
	if (now == n + 1) {
		ans = min(ans, cnt);
		return ;
	}
	for (int i = 1; i <= cnt; i++) {
		if (c[i] + a[now] <= w) {
			c[i] += a[now];
			dfs(now + 1, cnt);
			c[i] -= a[now];
		}
	}
	c[cnt + 1] = a[now];
	dfs(now + 1, cnt + 1);
	c[cnt + 1] = 0;
}


int main() {
	cin >> n >> w;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n, greater<int>());
	dfs(1, 0);
	cout << ans;
	return 0;
}