// Interprete a Distancia Manhattan em funcao de coordenadas dos pontos.
// defina entao um par e declare um vetor de pares
// lembre-se que o problema tem como posicao final os elementos em ordem crescente
// de 1 a 8. 0 representa o espaço vazio..

typedef vector<int> vi;

typedef pair<int, int> pii;


vi final={1,2,3,4,5,6,7,8,0};  //vetor final ...

pii manh[20];



// na funcao main faça

for (int i = 0; i < (int)final.size(); i++)
		manh[final[i]-'0'] = mp(i/3, i%3);


// e finalmente compute a DM.. de um determinado estao ao estado final 

int h_man(vi& s) {
	int ret = 0;
	for (int i = 0; i < (int)s.size(); i++) {
		if (s[i] != '0')
			ret += abs(manh[s[i]].first - i/3) + abs(manh[s[i]].second - i%3);
	}
	
	return ret;
}