9079

알고리즘/acmicpc 2015. 9. 13. 16:20 Posted by 아는 개발자

다익스트라를 이용해서 해결하면 간단하다. 여기서 오래 걸린거는 input값을 받는 것이다. scanf로 문자열을 받을때는 공백도 인식한다는 것에 주의해야하는데 그걸 알아채리지 못하고 쓸데 없이 시간을 많이 끌었다. 반성해야하는 부분이다...


 
#include<iostream>
#include<queue>
#include<cstdio>

using namespace std;

int d[(1<<9)];

const int MAX = 1<<9;

int allH = (1<<9)-1;
int allT = 0;

int edge[8][3] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
	{ 0, 3, 6 },
	{ 1, 4, 7 },
	{ 2, 5, 8 },
	{ 0, 4, 8 },
	{ 2, 4, 6 }
};

int main(){
	int tc, res;
	char tmp;

	cin>>tc;

	while(tc--){
		int cur=0, up=1;
		res=-1;

		for(int i=0; i<9; i++){
			cin>>tmp;
			if(tmp=='H')
				cur+=up;
			up*=2;
		}

		for(int i=0; i<MAX; i++)
			d[i]=-1;

		priority_queue<pair<int, int> > pq;
		pq.push(make_pair(0, cur));

		while(!pq.empty()){
			pair<int, int> front=pq.top();
			pq.pop();
			int cur_d=-front.first;
			int cur_p=front.second;
			
			if(d[cur_p]!=-1 && d[cur_p] <= cur_d)
				continue;
			d[cur_p]=cur_d;

			if(cur_p == allH || cur_p == allT){
				res = cur_d;
				break;
			}

			for(int i=0; i<8; i++){
				int next_p = cur_p;
				for(int j=0; j<3; j++){
					if(cur_p & (1<<edge[i][j]))
						next_p -= 1<<edge[i][j];
					else
						next_p += 1<<edge[i][j];
				}
				pq.push(make_pair(-(cur_d+1), next_p));
			}
		}
		printf("%d\n", res);
	}
}
728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13
2465  (0) 2015.09.08
2457  (0) 2015.09.04
2481  (0) 2015.09.01