• <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  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产精品久久久久久久|
成人亚洲欧美久久久久|
久久精品无码一区二区日韩AV
|
天天综合久久久网|
国产精品久久久久国产A级|
777午夜精品久久av蜜臀|
欧美性大战久久久久久|
久久夜色精品国产亚洲av|
久久精品国产亚洲AV无码麻豆|
亚洲精品无码久久不卡|
亚洲国产成人久久综合碰|
亚洲国产成人精品无码久久久久久综合
|
热re99久久精品国99热|
亚洲av成人无码久久精品|
亚洲香蕉网久久综合影视|
久久亚洲精品中文字幕|
久久精品毛片免费观看|
国产精品久久久久久影院
|
四虎国产精品免费久久久|
久久国产精品久久国产精品|
久久人搡人人玩人妻精品首页|
久久高清一级毛片|
久久免费看黄a级毛片|
婷婷五月深深久久精品|
97久久精品人妻人人搡人人玩|
狠狠色丁香久久婷婷综|
精品久久久久久无码免费|
无码国内精品久久人妻麻豆按摩|
99久久精品国产一区二区|
国内精品久久久久久久97牛牛|
情人伊人久久综合亚洲|
天天做夜夜做久久做狠狠|
亚洲综合伊人久久综合|
久久亚洲精品视频|
三级三级久久三级久久|
狠狠色婷婷久久一区二区三区|
99精品久久久久久久婷婷|
久久久亚洲AV波多野结衣
|
久久国产成人|
中文字幕热久久久久久久|
欧美久久综合性欧美|