代码
比这篇新的文章:
Codee#9301
比这篇旧的文章: Codee#9299
作者: yuechacmore, 点击63次, 评论(0), 收藏者(0), , 打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: Codee#9299
pku3322
语言: C++, 标签: BFS sky 2010/02/09发布 1个月前更新作者: yuechacmore, 点击63次, 评论(0), 收藏者(0), , 打分:
C++语言: pku3322
001 Source Code
002
003 Problem: 3322 User: 10074187
004 Memory: 9836K Time: 594MS
005 Language: C++ Result: Accepted
006 Source Code
007 /*http://acm.pku.edu.cn/JudgeOnline/problem?id=3322*/
008 #include <stdio.h>
009 #include <stdlib.h>
010 #include <memory.h>
011 #define MAXDIM 510
012 #define IN( a, b ) ( a >= 0 && a < r && b >= 0 && b < c )
013 #define ENQUEUE(); queue[ tail ].x = tx; queue[ tail ].y = ty; queue[ tail ].d = td; queue[ tail++ ].s = ss + 1;
014 #define INIT(); tx = xx + di[ dd ][ i ][ 0 ]; ty = yy + di[ dd ][ i ][ 1 ]; ttx = xx + di[ dd ][ i ][ 2 ]; tty = yy + di[ dd ][ i ][ 3 ];
015 int r, c;
016 char map[ MAXDIM ][ MAXDIM ];
017 int sx, sy, xx, yy, d;
018 struct Que
019 {
020 int x, y;
021 int d;
022 int s;
023 };
024 Que queue[ MAXDIM * MAXDIM * 3 ];
025 bool visited[ MAXDIM ][ MAXDIM ][ 3 ];
026 int di[ 3 ][ 4 ][ 4 ] =
027 {
028 { { -2, 0, -1, 0 }, { 1, 0, 2, 0 }, { 0, -2, 0, -1 }, { 0, 1, 0, 2 } },
029 { { -1, 0, -1, 1 }, { 1, 0, 1, 1 }, { 0, -1, 0, -1 }, { 0, 2, 0, 2 } },
030 { { 0, -1, 1, -1 }, { 0, 1, 1, 1 }, { -1, 0, -1, 0 }, { 2, 0, 2, 0 } }
031 };
032 int bfs()
033 {
034 memset( visited, 0, sizeof( visited ) );
035 queue[ 0 ].x = sx;
036 queue[ 0 ].y = sy;
037 queue[ 0 ].d = d;
038 queue[ 0 ].s = 0;
039 visited[ sx ][ sy ][ d ] = true;
040 int head, tail;
041 for( head = 0, tail = 1; head < tail; head++ )
042 {
043 int xx = queue[ head ].x;
044 int yy = queue[ head ].y;
045 int dd = queue[ head ].d;
046 int ss = queue[ head ].s;
047 int tx, ty, ttx, tty, td;
048 for( int i = 0; i < 4; i++ )
049 {
050 INIT();
051 if( dd == 0 )
052 {
053 if( i < 2 ) td = 2;
054 else td = 1;
055 }
056 else if( dd == 1 )
057 {
058 if( i < 2 ) td = 1;
059 else td = 0;
060 }
061 else
062 {
063 if( i < 2 ) td = 2;
064 else td = 0;
065 }
066 if( IN( tx, ty ) && IN( ttx, tty ) && map[ tx ][ ty ] != '#' && map[ ttx ][ tty ] != '#' && !visited[ tx ][ ty ][ td ] )
067 {
068 visited[ tx ][ ty ][ td ] = true;
069 if( !( td == 0 && map[ tx ][ ty ] == 'E' ) )
070 {
071 ENQUEUE();
072 if( td == 0 && map[ tx ][ ty ] == 'O' )
073 return ss + 1;
074 }
075 }
076 }
077 }
078 return -1;
079 }
080 int main()
081 {
082 int i, j;
083 while( scanf("%d %d", &r, &c), r || c )
084 {
085 for( i = 0; i < r; i++ )
086 scanf("%s", map[ i ]);
087 int count = 0;
088 xx = yy = -1;
089 for( i = 0; i < r; i++ )
090 for( j = 0; j < c; j++ )
091 if( map[ i ][ j ] == 'X' )
092 {
093 if( count == 0 )
094 {
095 sx = i;
096 sy = j;
097 count++;
098 }
099 else
100 {
101 xx = i;
102 yy = j;
103 count++;
104 }
105 }
106 if( sx == xx )
107 d = 1;
108 else if( sy == yy )
109 d = 2;
110 else
111 d = 0;
112 int flag = bfs();
113 if( flag == -1 )
114 printf("Impossible\n");
115 else
116 printf("%d\n", flag);
117 }
118 return 0;
119 }
002
003 Problem: 3322 User: 10074187
004 Memory: 9836K Time: 594MS
005 Language: C++ Result: Accepted
006 Source Code
007 /*http://acm.pku.edu.cn/JudgeOnline/problem?id=3322*/
008 #include <stdio.h>
009 #include <stdlib.h>
010 #include <memory.h>
011 #define MAXDIM 510
012 #define IN( a, b ) ( a >= 0 && a < r && b >= 0 && b < c )
013 #define ENQUEUE(); queue[ tail ].x = tx; queue[ tail ].y = ty; queue[ tail ].d = td; queue[ tail++ ].s = ss + 1;
014 #define INIT(); tx = xx + di[ dd ][ i ][ 0 ]; ty = yy + di[ dd ][ i ][ 1 ]; ttx = xx + di[ dd ][ i ][ 2 ]; tty = yy + di[ dd ][ i ][ 3 ];
015 int r, c;
016 char map[ MAXDIM ][ MAXDIM ];
017 int sx, sy, xx, yy, d;
018 struct Que
019 {
020 int x, y;
021 int d;
022 int s;
023 };
024 Que queue[ MAXDIM * MAXDIM * 3 ];
025 bool visited[ MAXDIM ][ MAXDIM ][ 3 ];
026 int di[ 3 ][ 4 ][ 4 ] =
027 {
028 { { -2, 0, -1, 0 }, { 1, 0, 2, 0 }, { 0, -2, 0, -1 }, { 0, 1, 0, 2 } },
029 { { -1, 0, -1, 1 }, { 1, 0, 1, 1 }, { 0, -1, 0, -1 }, { 0, 2, 0, 2 } },
030 { { 0, -1, 1, -1 }, { 0, 1, 1, 1 }, { -1, 0, -1, 0 }, { 2, 0, 2, 0 } }
031 };
032 int bfs()
033 {
034 memset( visited, 0, sizeof( visited ) );
035 queue[ 0 ].x = sx;
036 queue[ 0 ].y = sy;
037 queue[ 0 ].d = d;
038 queue[ 0 ].s = 0;
039 visited[ sx ][ sy ][ d ] = true;
040 int head, tail;
041 for( head = 0, tail = 1; head < tail; head++ )
042 {
043 int xx = queue[ head ].x;
044 int yy = queue[ head ].y;
045 int dd = queue[ head ].d;
046 int ss = queue[ head ].s;
047 int tx, ty, ttx, tty, td;
048 for( int i = 0; i < 4; i++ )
049 {
050 INIT();
051 if( dd == 0 )
052 {
053 if( i < 2 ) td = 2;
054 else td = 1;
055 }
056 else if( dd == 1 )
057 {
058 if( i < 2 ) td = 1;
059 else td = 0;
060 }
061 else
062 {
063 if( i < 2 ) td = 2;
064 else td = 0;
065 }
066 if( IN( tx, ty ) && IN( ttx, tty ) && map[ tx ][ ty ] != '#' && map[ ttx ][ tty ] != '#' && !visited[ tx ][ ty ][ td ] )
067 {
068 visited[ tx ][ ty ][ td ] = true;
069 if( !( td == 0 && map[ tx ][ ty ] == 'E' ) )
070 {
071 ENQUEUE();
072 if( td == 0 && map[ tx ][ ty ] == 'O' )
073 return ss + 1;
074 }
075 }
076 }
077 }
078 return -1;
079 }
080 int main()
081 {
082 int i, j;
083 while( scanf("%d %d", &r, &c), r || c )
084 {
085 for( i = 0; i < r; i++ )
086 scanf("%s", map[ i ]);
087 int count = 0;
088 xx = yy = -1;
089 for( i = 0; i < r; i++ )
090 for( j = 0; j < c; j++ )
091 if( map[ i ][ j ] == 'X' )
092 {
093 if( count == 0 )
094 {
095 sx = i;
096 sy = j;
097 count++;
098 }
099 else
100 {
101 xx = i;
102 yy = j;
103 count++;
104 }
105 }
106 if( sx == xx )
107 d = 1;
108 else if( sy == yy )
109 d = 2;
110 else
111 d = 0;
112 int flag = bfs();
113 if( flag == -1 )
114 printf("Impossible\n");
115 else
116 printf("%d\n", flag);
117 }
118 return 0;
119 }
所有评论，共0条：( 我也来说两句)