ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 9079
    알고리즘/acmicpc 2015. 9. 13. 16:20

    다익스트라를 이용해서 해결하면 간단하다. 여기서 오래 걸린거는 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);
    	}
    }
    

    '알고리즘 > 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

    댓글 0

Designed by Tistory.