백준] 3041 - N-퍼즐(COCI 2006/2007)

시간 제한 : 1초

메모리 제한 : 128MB

입력

4줄에 걸쳐 현재 퍼즐의 상태가 주어진다.

출력

퍼즐의 흩어짐 정도를 출력한다.

소스코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int abs(int a, int b)
{
	return a < b ? (b - a) : (a - b);
}
int main(void)
{
	int size = 4;
	vector<string> arr(4);
	for (int i = 0; i < size; i++)
		cin >> arr[i];

	int ans = 0;
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			if (arr[i][j] != '.')
				ans += abs(i, (arr[i][j] - 'A') / 4)+abs(j, (arr[i][j] - 'A') % 4);
	cout << ans;
}

Tip

처음에 이 문제를 어떻게 풀어야 하나 고민했는데, 빈칸을 뜻하는 '.'은 좌표로 계산할 필요가 없다. 따라서 알파벳들만 맨해튼 거리를 측정하면 된다. 맨해튼 거리에 대한 설명은 위키피디아를 참조하면 된다.