• <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)  編輯 收藏 引用  所屬分類: 搜索 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久人人爽人人爽人人片AV高清
|
91麻豆国产精品91久久久|
欧美久久久久久午夜精品|
国产精品乱码久久久久久软件|
亚洲精品乱码久久久久久
|
久久人人妻人人爽人人爽|
久久国产精品99精品国产987|
久久国产视屏|
99精品久久精品|
性色欲网站人妻丰满中文久久不卡|
精品久久久久久久|
人妻精品久久久久中文字幕69|
久久综合亚洲色HEZYO国产|
久久香蕉国产线看观看乱码|
国内高清久久久久久|
久久久国产一区二区三区|
久久亚洲欧美日本精品|
久久精品国产亚洲AV香蕉|
国内精品伊人久久久久777|
久久一区二区三区免费|
国产精品九九久久精品女同亚洲欧美日韩综合区
|
久久夜色精品国产噜噜麻豆|
久久亚洲国产精品五月天婷|
亚洲一区中文字幕久久|
久久久av波多野一区二区|
亚洲AV日韩精品久久久久久久|
欧美久久久久久午夜精品|
久久99精品国产麻豆蜜芽|
草草久久久无码国产专区|
国产精品视频久久|
久久99国产精品一区二区|
久久久国产精品网站|
国产精品久久网|
亚洲国产成人久久综合一|
国产成人综合久久久久久|
精品久久久久久久久久久久久久久|
久久91精品国产91久久户|
99久久亚洲综合精品成人|
久久久久久久久久免免费精品
|
色综合久久综合中文综合网|
麻豆AV一区二区三区久久|