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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久久久久九九99精品|
精品久久久久久国产牛牛app|
91精品国产9l久久久久|
久久久久夜夜夜精品国产|
国产精品久久久福利|
久久久精品日本一区二区三区
|
久久99精品久久只有精品|
亚洲国产成人久久一区久久|
奇米影视7777久久精品|
日本免费一区二区久久人人澡|
性做久久久久久久久老女人
|
久久影视综合亚洲|
久久天天躁狠狠躁夜夜2020一|
噜噜噜色噜噜噜久久|
青春久久|
国产一区二区精品久久岳|
少妇久久久久久久久久|
色婷婷狠狠久久综合五月|
91精品国产综合久久精品|
久久强奷乱码老熟女|
国产成人无码久久久精品一|
久久久久国色AV免费看图片|
好久久免费视频高清|
一级a性色生活片久久无少妇一级婬片免费放
|
久久国产精品成人片免费|
一本一本久久A久久综合精品
|
久久综合久久伊人|
美女写真久久影院|
国产精品热久久毛片|
国产成人综合久久综合|
91精品国产91久久综合|
国内精品久久久人妻中文字幕|
国内精品伊人久久久影院|
久久亚洲精品国产精品婷婷|
久久久一本精品99久久精品88|
国产成人精品综合久久久|
伊人久久综合成人网|
精品熟女少妇aⅴ免费久久|
久久久久久久女国产乱让韩|
亚洲精品无码久久久久|
久久人人爽人人精品视频|