• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			

            

            
	
            
		
			
            worm
            
			為什么我的眼里飽含淚水？因?yàn)槲页绦驔]寫完！
		            		
	
            

            

            

            

            隨筆 - 5, 文章 - 2, 評論 - 10, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			poj 3414解題報(bào)告(廣搜題)
		
            
		
            
		                郁悶?zāi)牵瑢懥似邆€小時，一直在調(diào)試錯誤了！fuck it！ 這個與別的BFS題的主要不同是要記錄正確順序的路徑,我用path[i][j] = {way，a,b}表示狀態(tài)（i，j）是由狀態(tài)（a，b）經(jīng)過方式way（一共六種方式）來得到的；呵呵，郁悶啊！
                           不過值得高興地是提交一次成功，呵呵，希望對大家有所幫助！下面是代碼，很亂，請大家湊合著看吧，現(xiàn)在是沒心情優(yōu)化了！！

              1//============================================================================
              2// Name        : poj.cpp
              3// Author      :
              4// Version     :
              5// Copyright   : Your copyright notice
              6// Description : BFS
              7//============================================================================
              8
              9#include <iostream>
             10#include <queue>
             11int A, B, C;
             12int j = 1;
             13int result[101][101] = { 0 };
             14using namespace std;
             15struct node {
             16    int a;
             17    int b;
             18}            ;
             19struct node2 {
             20    int pre;
             21    int m;
             22    int n;
             23}             path[101][101];
             24int p[1000];
             25int visited[101][101] = { 0 };
             26int BFS(node x) {
             27    queue<node> q;
             28    q.push(x);
             29    visited[x.a][x.b] = 1;
             30    result[x.a][x.b] = 0;
             31    path[x.a][x.b].pre = 0;
             32    path[0][0].m = path[0][0].n = 0;
             33    while (!q.empty()) {
             34        node temp = q.front();
             35        q.pop();
             36        if (temp.a == C)
             37            return temp.b;
             38        if (temp.b == C) {
             39            j = 2;
             40            return temp.a;
             41        }
             42        node y;
             43        y.a = A;
             44        y.b = temp.b;
             45        if (temp.a < A && !visited[A][temp.b]) {
             46            q.push(y);
             47            visited[A][temp.b] = 1;
             48            result[y.a][y.b] = result[temp.a][temp.b] + 1;
             49            path[y.a][y.b].pre = 1;
             50            path[y.a][y.b].m = temp.a;
             51            path[y.a][y.b].n = temp.b;
             52        }
             53        y.a = temp.a;
             54        y.b = B;
             55        if (temp.b < B && !visited[y.a][y.b]) {
             56            q.push(y);
             57            visited[temp.a][B] = 1;
             58            result[y.a][y.b] = result[temp.a][temp.b] + 1;
             59            path[y.a][y.b].pre = 2;
             60            path[y.a][y.b].m = temp.a;
             61            path[y.a][y.b].n = temp.b;
             62
             63        }
             64        y.a = 0;
             65        y.b = temp.b;
             66        if (temp.a != 0 && !visited[0][temp.b]) {
             67            q.push(y);
             68            visited[0][temp.b] = 1;
             69            result[y.a][y.b] = result[temp.a][temp.b] + 1;
             70            path[y.a][y.b].pre = 3;
             71            path[y.a][y.b].m = temp.a;
             72            path[y.a][y.b].n = temp.b;
             73
             74        }
             75
             76        y.a = temp.a;
             77        y.b = 0;
             78        if (temp.b != 0 && !visited[temp.a][0]) {
             79            q.push(y);
             80            visited[temp.a][0] = 1;
             81            result[y.a][y.b] = result[temp.a][temp.b] + 1;
             82            path[y.a][y.b].pre = 4;
             83            path[y.a][y.b].m = temp.a;
             84            path[y.a][y.b].n = temp.b;
             85
             86        }
             87        y.a = temp.a + temp.b - B;
             88        y.b = B;
             89        if (temp.a + temp.b > B && !visited[temp.a + temp.b - B][B]) {
             90            q.push(y);
             91            visited[temp.a + temp.b - B][B] = 1;
             92            result[y.a][y.b] = result[temp.a][temp.b] + 1;
             93            path[y.a][y.b].pre = 5;
             94            path[y.a][y.b].m = temp.a;
             95            path[y.a][y.b].n = temp.b;
             96
             97        }
             98        y.a = 0;
             99        y.b = temp.a + temp.b;
            100        if (temp.a + temp.b <= B && !visited[0][temp.a + temp.b]) {
            101            q.push(y);
            102            visited[0][temp.a + temp.b] = 1;
            103            result[y.a][y.b] = result[temp.a][temp.b] + 1;
            104            path[y.a][y.b].pre = 5;
            105            path[y.a][y.b].m = temp.a;
            106            path[y.a][y.b].n = temp.b;
            107
            108        }
            109        y.a = A;
            110        y.b = temp.a + temp.b - A;
            111        if (temp.a + temp.b > A && !visited[A][temp.a + temp.b - A]) {
            112            q.push(y);
            113            visited[A][temp.a + temp.b - A] = 1;
            114            result[y.a][y.b] = result[temp.a][temp.b] + 1;
            115            path[y.a][y.b].pre = 6;
            116            path[y.a][y.b].m = temp.a;
            117            path[y.a][y.b].n = temp.b;
            118        }
            119        y.a = temp.a + temp.b;
            120        y.b = 0;
            121        if (temp.a + temp.b <= A && !visited[temp.a + temp.b][0]) {
            122            q.push(y);
            123            visited[temp.a + temp.b][0] = 1;
            124            result[y.a][y.b] = result[temp.a][temp.b] + 1;
            125            path[y.a][y.b].pre = 6;
            126            path[y.a][y.b].m = temp.a;
            127            path[y.a][y.b].n = temp.b;
            128
            129        }
            130    }
            131    return -1;
            132}
            133int main() {
            134    cin >> A >> B >> C;
            135    int i = 1;
            136    int ff;
            137    node x;
            138    x.a = 0;
            139    x.b = 0;
            140    int m = BFS(x);
            141    if (m == -1) {
            142        cout << "impossible" << endl;
            143        return 0;
            144    }
            145    if (j == 1) {
            146        ff = result[C][m];
            147        cout << result[C][m] << endl;
            148        int x = C;
            149        int y = m;
            150        while (path[x][y].pre != 0) {
            151            p[i++] = path[x][y].pre;
            152            int temp1 = x;
            153            int temp2 = y;
            154            x = path[temp1][temp2].m;
            155            y = path[temp1][temp2].n;
            156        }
            157    }
            158    if (j == 2) {
            159        ff = result[m][C];
            160        cout << result[m][C] << endl;
            161        int x = m;
            162        int y = C;
            163        while (path[x][y].pre != 0) {
            164            p[i++] = path[x][y].pre;
            165            int temp1 = x;
            166            int temp2 = y;
            167            x = path[temp1][temp2].m;
            168            y = path[temp1][temp2].n;
            169        }
            170    }
            171    for (int i = ff; i >= 1; i--) {
            172        switch (p[i]) {
            173        case 1:
            174            cout << "FILL(1)" << endl;
            175            break;
            176        case 2:
            177            cout << "FILL(2)" << endl;
            178            break;
            179        case 3:
            180            cout << "DROP(1)" << endl;
            181            break;
            182        case 4:
            183            cout << "DROP(2)" << endl;
            184            break;
            185        case 5:
            186            cout << "POUR(1,2)" << endl;
            187            break;
            188        case 6:
            189            cout << "POUR(2,1)" << endl;
            190            break;
            191        }
            192
            193    }
            194    return 0;
            195}
            196
            

		
            
		
            
			posted on 2009-03-08 18:40 WORM 閱讀(1660) 評論(5)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				
            
					# re: poj 3414解題報(bào)告(廣搜題)[未登錄]  回復(fù)  更多評論
					  
				
            
				垃圾 
				
            
					2009-03-08 18:59 | A
				
            
			
            
		
			
            
				
            
					# re: poj 3414解題報(bào)告(廣搜題)  回復(fù)  更多評論
					  
				
            
				@A 我承認(rèn)本人是菜鳥，你牛逼你來搜人家的解題報(bào)告干嘛啊？？

            
				
            
					2009-03-08 19:03 | WORM
				
            
			
            
		
			
            
				
            
					# re: poj 3414解題報(bào)告(廣搜題)[未登錄]  回復(fù)  更多評論
					  
				
            
				我不是搜，訂閱到博客天天是解體報(bào)告。。
				
            
					2009-03-08 19:55 | A
				
            
			
            
		
			
            
				
            
					# re: poj 3414解題報(bào)告(廣搜題)  回復(fù)  更多評論
					  
				
            
				已閱 刪之
				
            
					2009-03-08 20:24 | cppexplore
				
            
			
            
		
			
            
				
            
					# re: poj 3414解題報(bào)告(廣搜題)  回復(fù)  更多評論
					  
				
            
				那我寫啥？@A

            
				
            
					2009-03-08 20:56 | WORM
				
            
			
            
		

            





            



            


            

	
            
		
		
            只有注冊用戶登錄后才能發(fā)表評論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产精品禁18久久久夂久|
久久综合给合综合久久|
久久99国产精品尤物|
国产精品无码久久久久|
亚洲国产视频久久|
久久综合综合久久狠狠狠97色88|
看全色黄大色大片免费久久久|
奇米综合四色77777久久|
国产精品九九久久精品女同亚洲欧美日韩综合区|
一级做a爰片久久毛片16|
久久人人爽人人爽人人av东京热|
丰满少妇高潮惨叫久久久|
亚洲午夜福利精品久久|
久久综合欧美成人|
天堂久久天堂AV色综合|
日韩一区二区三区视频久久|
久久久久亚洲av无码专区导航|
久久青青草原精品国产软件|
国产精品视频久久久|
久久精品国产99国产精品亚洲|
久久强奷乱码老熟女网站|
香港aa三级久久三级|
久久精品国产久精国产思思|
久久无码高潮喷水|
青春久久|
久久亚洲国产精品123区|
国产亚洲成人久久|
www.久久热.com|
99久久精品毛片免费播放|
亚洲国产精品无码久久久不卡|
久久中文字幕精品|
久久久久亚洲国产|
人妻精品久久久久中文字幕|
性做久久久久久久久老女人|
久久免费香蕉视频|
久久亚洲精品无码观看不卡|
久久久精品波多野结衣|
久久亚洲国产精品五月天婷|
伊色综合久久之综合久久|
精品久久人人爽天天玩人人妻|
成人久久免费网站|