• <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++博客 ::
首頁(yè) ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評(píng)論
				::
				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 巫 閱讀(174) 評(píng)論(0)  編輯 收藏 引用  所屬分類: 搜索 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久人人妻人人爽人人爽|
99久久精品免费看国产一区二区三区
|
久久婷婷五月综合国产尤物app|
久久青青草原亚洲av无码app|
一本久道久久综合狠狠躁AV|
激情久久久久久久久久|
国产精品久久国产精品99盘
|
亚洲中文字幕无码一久久区|
久久久精品久久久久特色影视|
9999国产精品欧美久久久久久|
91久久精品国产成人久久|
欧美日韩中文字幕久久伊人|
久久青青草原综合伊人|
国产精品久久久久久久久鸭
|
超级碰久久免费公开视频|
中文字幕亚洲综合久久|
久久精品成人|
亚洲国产成人乱码精品女人久久久不卡|
久久se精品一区精品二区国产|
日本久久久精品中文字幕|
久久精品成人欧美大片|
婷婷久久综合九色综合绿巨人|
奇米影视7777久久精品人人爽|
久久亚洲AV成人无码国产|
国产精品美女久久久久|
精品国产婷婷久久久|
亚洲欧洲中文日韩久久AV乱码|
亚洲国产另类久久久精品黑人|
久久亚洲国产欧洲精品一|
久久国产精品国语对白|
亚洲国产精品高清久久久|
97精品国产97久久久久久免费|
亚洲国产小视频精品久久久三级|
亚洲AV无码一区东京热久久|
香蕉久久一区二区不卡无毒影院|
亚洲国产日韩欧美综合久久|
精品综合久久久久久97超人|
深夜久久AAAAA级毛片免费看|
久久精品无码专区免费青青
|
国产精品热久久毛片|
久久久久久久久久久久中文字幕
|