|
10 Seconds Memory Limit: 32768 KB At 17:00, special agent Jack starts to escape from the enemy camp. There is a cliff in between the camp and the nearest safety zone. Jack has to climb the almost vertical cliff by stepping his feet on the blocks that cover the Figure D-1 shows an example of cliff data that you will receive. The cliff is covered with square blocks. Jack starts cliff climbing from the ground under the cliff, by stepping his left or right foot on one of the blocks marked
Jack's movement must meet the following constraints. After putting his left (or right) foot on a block, he can only move his right (or left, respectively) foot. His left foot position (lx,
Input The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows:
The integers w and h are the width and the height of the matrix data of the cliff. You may assume 2 <=
You can assume that it takes no time to put a foot on a block marked with 'S' or 'T'. Output For each dataset, print a line only having a decimal integer indicating the minimum time required for the cliff climbing, when Jack can complete it. Otherwise, print a line only having "-1" for the dataset. Each line should not Sample Input 6 6
4 4 X X T T
4 7 8 2 X 7
3 X X X 1 8
1 2 X X X 6
1 1 2 4 4 7
S S 2 3 X X
2 10
T 1
1 X
1 X
1 X
1 1
1 X
1 X
1 1
1 X
S S
2 10
T X
1 X
1 X
1 X
1 1
1 X
1 X
1 1
1 X
S S
10 10
T T T T T T T T T T
X 2 X X X X X 3 4 X
9 8 9 X X X 2 9 X 9
7 7 X 7 3 X X 8 9 X
8 9 9 9 6 3 X 5 X 5
8 9 9 9 6 X X 5 X 5
8 6 5 4 6 8 X 5 X 5
8 9 3 9 6 8 X 5 X 5
8 3 9 9 6 X X X 5 X
S S S S S S S S S S
10 7
2 3 2 3 2 3 2 3 T T
1 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 4
3 2 3 2 3 2 3 2 3 5
3 2 3 1 3 2 3 2 3 5
2 2 3 2 4 2 3 2 3 5
S S 2 3 2 1 2 3 2 3
0 0
Sample Output 12
5
-1
22
12
Source: Japan Domestic Contest 2007 Status |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 70
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,ans;
char mp[maxn][maxn];
int dist[maxn][maxn][2];
bool vis[maxn][maxn][2];
int dx1[]= {0,0,0,-1,-1,-2,1,1,2};
int dy1[]= {1,2,3,1,2,1,1,2,1};
int dx2[]= {0,0,0,-1,-1,-2,1,1,2};
int dy2[]= {-1,-2,-3,-1,-2,-1,-1,-2,-1};
char s[5];
struct Node
{
int x,y;
int flag;
} cur,now;
queue<Node>q;
void init()
{
while(!q.empty()) q.pop();
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
}
void SPFA()
{
int i,j,t,nx,ny,tx,ty;
while(!q.empty())
{
now=q.front();
q.pop();
nx=now.x;
ny=now.y;
vis[nx][ny][now.flag]=0;
if(!now.flag) // 左脚落地移右脚
{
for(i=0; i<9; i++)
{
tx=nx+dx1[i];
ty=ny+dy1[i];
if(!(tx>=1&&tx<=n&&ty>=1&&ty<=m)) continue ;
if(mp[tx][ty]=='X') continue ;
if(mp[tx][ty]=='S'||mp[tx][ty]=='T') t=0;
else t=mp[tx][ty]-'0';
if(dist[tx][ty][1]>dist[nx][ny][0]+t)
{
dist[tx][ty][1]=dist[nx][ny][0]+t;
if(!vis[tx][ty][1])
{
vis[tx][ty][1]=1;
cur.x=tx;
cur.y=ty;
cur.flag=1;
q.push(cur);
}
}
}
}
else // 右脚落地移左脚
{
for(i=0; i<9; i++)
{
tx=nx+dx2[i];
ty=ny+dy2[i];
if(!(tx>=1&&tx<=n&&ty>=1&&ty<=m)) continue ;
if(mp[tx][ty]=='X') continue ;
if(mp[tx][ty]=='S'||mp[tx][ty]=='T') t=0;
else t=mp[tx][ty]-'0';
if(dist[tx][ty][0]>dist[nx][ny][1]+t)
{
dist[tx][ty][0]=dist[nx][ny][1]+t;
if(!vis[tx][ty][0])
{
vis[tx][ty][0]=1;
cur.x=tx;
cur.y=ty;
cur.flag=0;
q.push(cur);
}
}
}
}
}
}
int main()
{
int i,j,k,mi;
while(scanf("%d%d",&m,&n),m||n)
{
init();
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%s",s);
mp[i][j]=s[0];
if(s[0]=='S')
{
dist[i][j][0]=dist[i][j][1]=0;
vis[i][j][0]=vis[i][j][1]=1;
cur.x=i;
cur.y=j;
cur.flag=0;
q.push(cur);
cur.flag=1;
q.push(cur);
}
}
}
SPFA();
ans=INF;
for(i=1; i<=m; i++)
{
if(mp[1][i]=='T')
{
mi=min(dist[1][i][0],dist[1][i][1]);
if(ans>mi) ans=mi;
}
}
if(ans==INF) ans=-1;
printf("%d\n",ans);
}
return 0;
}