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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              1#include <cstdio>
              2#include <cstring>
              3
              4const int MAXE = 80;
              5const int MAXN = 60;
              6const int SIZE = 5000;
              7
              8struct NODE
              9{
             10    char m_cMark;
             11    int m_pre;
             12    int m_x, m_y;
             13}            Q[SIZE];
             14
             15int N, E, g_start_x, g_start_y, g_end;
             16char map[MAXN][MAXE];
             17bool visited[MAXN][MAXE];
             18
             19void BFS()
             20{
             21    int h = 0, t = 1;
             22    NODE temp;
             23    visited[g_start_x][g_start_y] = true;
             24    Q[0].m_x = g_start_x;
             25    Q[0].m_y = g_start_y;
             26
             27    while ( h <= t )
             28    {
             29        temp = Q[h];
             30
             31        if ( map[temp.m_x][temp.m_y] =='E' )
             32        {
             33            g_end = temp.m_pre;
             34            break;
             35        }
             36
             37        if ( temp.m_x > 0 &&  !visited[temp.m_x - 1][temp.m_y] )
             38        {
             39            visited[temp.m_x - 1][temp.m_y] = true;
             40            Q[t].m_x = temp.m_x - 1;
             41            Q[t].m_y = temp.m_y;
             42            Q[t].m_pre = h;
             43            Q[t].m_cMark = 'N';
             44            if ( map[temp.m_x - 1][temp.m_y] == '+' )
             45                Q[t].m_cMark = '+' ;
             46            t++;
             47
             48        }
             49        if ( temp.m_y + 1 < E &&  !visited[temp.m_x][temp.m_y + 1] )
             50        {
             51            visited[temp.m_x][temp.m_y + 1] = true;
             52            Q[t].m_x = temp.m_x;
             53            Q[t].m_y = temp.m_y + 1;
             54            Q[t].m_pre = h;
             55            Q[t].m_cMark = 'E';
             56            if ( map[temp.m_x][temp.m_y + 1] == '+' )
             57                Q[t].m_cMark = '+' ;
             58            t++;
             59        }
             60        if ( temp.m_x + 1 < N &&  !visited[temp.m_x + 1][temp.m_y] )
             61        {
             62            visited[temp.m_x + 1][temp.m_y] = true;
             63            Q[t].m_x = temp.m_x + 1;
             64            Q[t].m_y = temp.m_y;
             65            Q[t].m_pre = h;
             66            Q[t].m_cMark = 'S';
             67            if ( map[temp.m_x + 1][temp.m_y] == '+' )
             68                Q[t].m_cMark = '+' ;
             69            t++;
             70        }
             71        if ( temp.m_y > 0 &&  !visited[temp.m_x][temp.m_y - 1] )
             72        {
             73            visited[temp.m_x][temp.m_y - 1] = true;
             74            Q[t].m_x = temp.m_x;
             75            Q[t].m_y = temp.m_y - 1;
             76            Q[t].m_pre = h;
             77            Q[t].m_cMark = 'W';
             78            if ( map[temp.m_x][temp.m_y - 1] == '+' )
             79                Q[t].m_cMark = '+' ;
             80            t++;
             81        }
             82
             83        h++;
             84    }
             85}
             86
             87int main()
             88{
             89//    freopen("1.txt", "r", stdin);
             90    int i, j, len;
             91    char ch, result[SIZE];
             92
             93    scanf("%d %d", &N, &E);
             94
             95    N = (N << 1) - 1, E = (E << 1) - 1;
             96
             97    memset(visited, 0, sizeof(visited));
             98    getchar();
             99    for ( i = 0; i < N; ++i )
            100    {
            101        for ( j = 0; j < E; ++j )
            102        {
            103            ch = getchar();
            104            map[i][j] = ch;
            105            if ( ch == 'S' )
            106            {
            107                g_start_x = i;
            108                g_start_y = j;
            109            }
            110            else if ( ch == '.' )
            111            {
            112                visited[i][j] = true;
            113            }
            114        }
            115        getchar();
            116    }
            117
            118    BFS();
            119
            120    i = g_end, len = 0;
            121    while ( i != 0 )
            122    {
            123        if ( Q[i].m_cMark != '+' )
            124        {
            125            result[len++] = Q[i].m_cMark;
            126        }
            127        i = Q[i].m_pre;
            128    }
            129
            130    i = len - 1, j = 1;
            131
            132    len -= 2;
            133    while ( len >= 0 )
            134    {
            135        if ( result[len] == result[i] ) {
            136            j++;
            137        }
            138        else {
            139            printf("%c %d\n", result[i], j);
            140            i = len;
            141            j = 1;
            142        }
            143        len--;
            144    }
            145    printf("%c %d\n", result[i], j);
            146
            147    return 0;
            148}
            

	
            
	
	
            
		posted on 2009-04-02 14:39 巫 閱讀(176) 評論(0)  編輯 收藏 引用  所屬分類: 搜索 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲精品无码久久久|
午夜精品久久久久久毛片|
韩国免费A级毛片久久|
久久久久一区二区三区|
久久99热这里只有精品国产|
久久亚洲电影|
久久亚洲精品视频|
亚洲人成伊人成综合网久久久|
久久久久久精品成人免费图片|
国产综合成人久久大片91|
久久偷看各类wc女厕嘘嘘|
久久涩综合|
久久久噜噜噜久久|
欧洲国产伦久久久久久久
|
久久亚洲欧美国产精品|
久久AAAA片一区二区|
国产精品热久久毛片|
国产精品美女久久久免费|
97久久精品国产精品青草|
麻豆精品久久久一区二区|
久久国产精品-国产精品|
日产久久强奸免费的看|
怡红院日本一道日本久久
|
久久精品亚洲精品国产色婷|
久久久久人妻一区精品色|
国产精品久久久久久久久鸭|
精品久久久无码中文字幕|
一级a性色生活片久久无
|
久久99国产精品尤物|
91精品国产高清久久久久久国产嫩草|
精品一区二区久久久久久久网站|
99久久免费国产精品|
波多野结衣久久|
久久精品成人一区二区三区|
伊人久久成人成综合网222|
9999国产精品欧美久久久久久|
午夜人妻久久久久久久久|
成人久久免费网站|
久久人人爽人人人人片av|
青青久久精品国产免费看|
欧美精品一区二区精品久久|