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

    
            

            




            







												


        

            
	

            misschuer
            

            

            


            
	
		

            常用鏈接
            

		

            統(tǒng)計
            
	
		

            積分與排名
            


		
		
            百事通
            
		
				
			
	

		

            最新評論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			zoj 1002 Fire Net
		
            
		
            http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
              1            #include <iostream>
              2#include <queue>
              3#define M 6
              4using namespace std;
              5
              6typedef struct point{
              7    int i , j, cnt;
              8    friend bool operator < (point a, point b){
              9        return a.cnt < b.cnt;
             10    }
             11}            point;
             12
             13priority_queue <point> Q;
             14char str[ M ][ M ];
             15int n , cnt;
             16
             17void endeavor (int x , int y){
             18//a point has four directions
             19//for each piont we could divide into five Situations: None direct has wall , One  , Two  ,Three  , Four ;
             20    int i , j;
             21    cnt = 0;
             22    for (i = y + 1;i < n;++ i){
             23        if (str[ x ][ i ] == 'X'){
             24            cnt ++ ; break;
             25        }
             26    }
             27
             28    for (i = y - 1;i >= 0;-- i){
             29        if (str[ x ][ i ] == 'X'){
             30            cnt ++ ; break;
             31        }
             32    }
             33
             34    for (i = x + 1;i < n;++ i){
             35        if (str[ i ][ y ] == 'X'){
             36            cnt ++ ; break;
             37        }
             38    }
             39
             40    for (i = x - 1;i >= 0;-- i){
             41        if (str[ i ][ y ] == 'X'){
             42            cnt ++ ; break;
             43        }
             44    }
             45
             46}
             47
             48void init (){
             49    point p;
             50    for (int i = 0;i < n;++ i){
             51        for (int j = 0;j < n;++ j){
             52            if (str[ i ][ j ] == '.'){
             53                p.i = i; p.j = j;
             54                endeavor(i , j);
             55                p.cnt = cnt;
             56                Q.push(p);
             57            }
             58        }
             59    }
             60}
             61
             62void recover (int x , int y){
             63    int i , j;
             64    for (i = y + 1;i < n;++ i){
             65        if (str[ x ][ i ] == 'X') break;
             66        str[ x ][ i ] = 'N';
             67    }
             68
             69    for (i = y - 1;i >= 0;-- i){
             70        if (str[ x ][ i ] == 'X') break;
             71        str[ x ][ i ] = 'N';
             72    }
             73
             74    for (i = x + 1;i < n;++ i){
             75        if (str[ i ][ y ] == 'X') break;
             76        str[ i ][ y ] = 'N';
             77    }
             78
             79    for (i = x - 1;i >= 0;-- i){
             80        if (str[ i ][ y ] == 'X') break;
             81        str[ i ][ y ] = 'N';
             82    }
             83}
             84
             85void GY (){
             86    point p;int ans = 0;
             87    while (!Q.empty()){
             88        p = Q.top();
             89        Q.pop();
             90        if (str[p.i][p.j] == '.'){
             91            ans ++;
             92            str[p.i][p.j] = 'O';
             93            recover (p.i , p.j);
             94        }
             95        else continue;
             96    }
             97    cout << ans << endl;
             98}
             99
            100int main(){
            101    while (cin >> n && n){
            102        for (int i = 0;i < n;++ i){
            103            cin >> str[ i ];
            104        }
            105        init ();
            106        GY ();
            107    }
            108    return 0;
            109}

            還有一種可用圖論做
            網(wǎng)絡(luò)流或者二分圖的最大匹配
            對于每行每列的連通塊定義一個不同的編號,然后上面的算法選一個算

            
		
            
			posted on 2010-04-24 13:03 此最相思 閱讀(247) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            



            


            

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

            


            

            		
		
            
	
            	

            



            

				

            



    
    







            
	   
	



亚洲精品无码久久久久去q|
久久这里只有精品久久|
久久人做人爽一区二区三区|
2021国内久久精品|
久久综合给合久久狠狠狠97色69|
久久天天躁狠狠躁夜夜avapp|
韩国三级大全久久网站|
麻豆国内精品久久久久久|
免费久久人人爽人人爽av|
久久香蕉综合色一综合色88|
久久综合久久性久99毛片|
久久精品国产乱子伦|
久久精品国产91久久综合麻豆自制
|
亚洲国产精品热久久|
久久久久免费视频|
久久99精品久久久久久久久久|
久久精品亚洲精品国产欧美|
欧美熟妇另类久久久久久不卡
|
亚洲精品国产自在久久|
俺来也俺去啦久久综合网|
久久精品国产国产精品四凭|
国产V综合V亚洲欧美久久|
99久久精品免费看国产一区二区三区|
久久精品一区二区三区不卡|
久久综合九色综合网站|
久久青青草原精品国产软件|
久久99国产综合精品|
亚洲狠狠婷婷综合久久久久|
久久久久久久亚洲精品|
91超碰碰碰碰久久久久久综合|
久久久噜噜噜www成人网|
午夜精品久久久内射近拍高清|
麻豆精品久久久一区二区|
88久久精品无码一区二区毛片|
亚洲精品美女久久久久99|
亚洲中文字幕伊人久久无码|
久久国产视屏|
久久久久久无码国产精品中文字幕
|
青青久久精品国产免费看|
国产精品九九久久免费视频
|
日日狠狠久久偷偷色综合0|