去年做杭州网赛的时候遇到的题目,当时一点思路都没有,过后一直没去做,今天看了一下,发现其实和hdu的1044很像,可以先缩图,然后bfs,我用了两次bfs实现。具体思路是对于每一个非墙非走廊的点进行bfs,扩展和它相邻的非墙非走廊的点,保存到邻接表中,然后对于所有边界上是gate的点进行bfs,用优先队列实现,状态为三维,即坐标+内力,其实可以将每个点离散化到一个数字,以减少内存开销来换取时间。
代码如下:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[4][2] =
{
{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{
int x;
int y;
int num;
int step;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool friend operator < (point a, point b)
{
return a.step > b.step;
}
}temp, tt;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char map[110][110];
vector < point > vec[101][101];
int n, m;
int hash[101][101];
priority_queue < point > q;
__int8 visit[100][100][27];
int ans;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//缩图
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void bfs(int x, int y)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
temp.x = x;
temp.y = y;
memset(hash, 0, sizeof(hash));
while(!q.empty() )
q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
q.push( temp );
hash[ temp.x ][ temp.y ] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!q.empty())
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
temp = q.top();
q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < 4; i++)
{
tt.x = temp.x + dir[i][0];
tt.y = temp.y + dir[i][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(tt.x < 0 || tt.y < 0 || tt.x == n || tt.y == m)
continue;
if(map[tt.x][tt.y] == '*')
continue;
if(map[tt.x][tt.y] >= 'A' && map[tt.x][tt.y] <= 'Z')
continue;
if(map[tt.x][tt.y] == '#')
continue;
if(hash[ tt.x ][ tt.y ])
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!hash[ tt.x ][ tt.y ] )
{
hash[ tt.x ][ tt.y ] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(map[tt.x][tt.y] == '.')
q.push( tt );
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
vec[x][y].push_back( tt );
}
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//求最短距离
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int BFS(int x, int y, int num)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
temp.step = 0;
temp.x = x;
temp.y = y;
temp.num = num;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(!q.empty())
q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(visit, -1, sizeof(visit));
q.push( temp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
visit[ temp.x ][ temp.y ][ temp.num ] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while( !q.empty() )
{
temp = q.top();
q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(temp.step > ans && ans != -1)
return -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if( map[ temp.x ][ temp.y ] == '$')
return temp.step;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int size = vec[ temp.x ][ temp.y ].size();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < size; i++)
{
point rt = vec[ temp.x ][ temp.y ][ i ];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[rt.x][rt.y] == '$')
{
tt.num = temp.num;
tt.step = temp.step;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tt.x = rt.x;
tt.y = rt.y;
if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
|| visit[ tt.x ][ tt.y ][ tt.num ] == -1)
{
visit[ tt.x ][ tt.y ][ tt.num ] = tt.step;
q.push( tt );
}
continue;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(temp.num)
{
tt.num = temp.num - 1;
tt.step = temp.step;
tt.x = rt.x;
tt.y = rt.y;
if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
|| visit[ tt.x ][ tt.y ][ tt.num ] == -1)
{
visit[ tt.x ][ tt.y ][ tt.num ] = tt.step;
q.push( tt );
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tt.num = temp.num;
tt.step = temp.step + map[rt.x][rt.y] - '0';
tt.x = rt.x;
tt.y = rt.y;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(tt.step < visit[ tt.x ][ tt.y ][ tt.num ]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
|| visit[ tt.x ][ tt.y ][ tt.num ] == -1)
{
visit[ tt.x ][ tt.y ][ tt.num ] = tt.step;
q.push( tt );
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(1)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(gets(map[0]))
{
if( strcmp(map[0], "") )
break;
}
m = strlen( map[0] );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(strcmp(map[0], "--") == 0)
break;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
n = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(gets(map[n]))
{
if(strcmp( map[n], "" ) == 0)
break;
else
n ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
for(j = 0;j < m; j++)
vec[i][j].clear();
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j < m; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j] >= '1' && map[i][j] <= '9')
{
bfs(i, j);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j] >= 'A' && map[i][j] <= 'Z' || map[i][j] == '#')
{
bfs(i, j);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j < m; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j] >= 'A' && map[i][j] <= 'Z')
{
int ty = BFS(i, j, map[i][j]-'A'+1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ty != -1)
{
if(ty < ans || ans == -1)
ans = ty;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j] == '#')
{
int ty = BFS(i, j, 0);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ty != -1)
{
if(ty < ans || ans == -1)
ans = ty;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(ans == -1)
printf("IMPOSSIBLE\n");
else
printf("%d\n", ans);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}