gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2435-- Navigating the City
  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 巫 阅读(160) 评论(0)  编辑 收藏 引用 所属分类: 搜索

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理