• <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
            
			為什么我的眼里飽含淚水？因為我程序沒寫完！
		            		
	
            

            

            

            

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

            


            		
	
            

            

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

              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 閱讀(1666) 評論(5)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

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

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

            
				
            
					2009-03-08 20:56 | WORM
				
            
			
            
		

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



久久精品国产清高在天天线|
久久精品亚洲日本波多野结衣|
久久久中文字幕|
精品国产乱码久久久久久1区2区
|
久久国产精品77777|
久久精品水蜜桃av综合天堂|
亚洲AV日韩精品久久久久久
|
久久久久久国产精品美女
|
色综合久久无码中文字幕|
久久久久亚洲av无码专区导航
|
一级做a爱片久久毛片|
国产高潮久久免费观看|
亚洲欧美另类日本久久国产真实乱对白
|
久久综合久久综合亚洲|
国产精品久久久久久久app|
久久久久久伊人高潮影院|
亚洲精品无码久久一线|
国产精品九九九久久九九|
中文字幕一区二区三区久久网站|
www.久久热.com|
成人综合久久精品色婷婷|
7777久久亚洲中文字幕|
久久亚洲国产精品五月天婷|
精品综合久久久久久97|
久久国产亚洲精品|
久久久久99精品成人片欧美|
久久强奷乱码老熟女网站|
青青青青久久精品国产h久久精品五福影院1421
|
久久天天躁狠狠躁夜夜av浪潮|
精品久久久久久国产潘金莲|
久久久久亚洲AV成人网人人网站|
久久精品国产72国产精福利|
国产免费福利体检区久久|
国产精品亚洲综合专区片高清久久久|
激情伊人五月天久久综合
|
国产亚州精品女人久久久久久
|
欧美午夜A∨大片久久
|
一本一道久久精品综合|
嫩草影院久久99|
久久国产精品免费一区|
久久五月精品中文字幕|