2014
01-05

# Cliff Climbing

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 cliff. The cliff has slippery blocks where Jack has to spend time to take each step. He also has to bypass some blocks that are too loose to support his weight. Your mission is to write a program that calculates the minimum time to complete climbing.

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 with ‘S’ at the bottom row. The numbers on the blocks are the "slippery levels". It takes t time units for him to safely put his foot on a block marked with t, where 1 ≤ t ≤ 9. He cannot put his feet on blocks marked with ‘X’. He completes the climbing when he puts either of his feet on one of the blocks marked with ‘T’ at the top row.

Figure D-1: Example of Cliff Data

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, ly) and his right foot position (rx, ry) should satisfy lx < rx and | lx – rx | + | ly – ry | ≤ 3. This implies that, given a position of his left foot in Figure D-2 (a), he has to place his right foot on one of the nine blocks marked with blue color. Similarly, given a position of his right foot in Figure D-2 (b), he has to place his left foot on one of the nine blocks marked with blue color.

Figure D-2: Possible Placements of Feet

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:

w h
s(1,1) … s(1,w)
s(2,1) … s(2,w)

s(h,1) … s(h,w)

The integers w and h are the width and the height of the matrix data of the cliff. You may assume 2 ≤ w ≤ 30 and 5 ≤ h ≤ 60. Each of the following h lines consists of w characters delimited by a space. The character s(y, x) represents the state of the block at position (x, y) as follows:

* ‘S’: Jack can start cliff climbing from this block.
* ‘T’: Jack finishes climbing when he reaches this block.
* ‘X’: Jack cannot put his feet on this block.
* ’1′ – ’9′ (= t): Jack has to spend t time units to put either of his feet on this block.

You can assume that it takes no time to put a foot on a block marked with ‘S’ or ‘T’.

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:

w h
s(1,1) … s(1,w)
s(2,1) … s(2,w)

s(h,1) … s(h,w)

The integers w and h are the width and the height of the matrix data of the cliff. You may assume 2 ≤ w ≤ 30 and 5 ≤ h ≤ 60. Each of the following h lines consists of w characters delimited by a space. The character s(y, x) represents the state of the block at position (x, y) as follows:

* ‘S’: Jack can start cliff climbing from this block.
* ‘T’: Jack finishes climbing when he reaches this block.
* ‘X’: Jack cannot put his feet on this block.
* ’1′ – ’9′ (= t): Jack has to spend t time units to put either of his feet on this block.

You can assume that it takes no time to put a foot on a block marked with ‘S’ or ‘T’.

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

12
5
-1
22
12

Problem – 2312

一条很暴力，有点恶心的搜索。题意其实很简单，主要是pfs的时候拓展结点会有种麻烦的感觉。注意的是，这里的n和m跟平常见到的有所不同，交换过来了。我的代码就是在因为这个长宽的问题wa了一次。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cctype>

using namespace std;

typedef pair<int, int> PII;
typedef pair<PII, PII> PPP;
typedef pair<int, PPP> PPPI;

#define FI first
#define SE second
#define PRIQ priority_queue

const int R = 66;
const int C = 33;
char mat[R][C];
bool vis[R][C][R][C];
int n, m;

inline int dis(int a, int b, int c, int d) { return abs(a - c) + abs(b - d);}
inline bool inmat(int a, int b) { return 0 <= a && a < n && 0 <= b && b < m;}

int work() {
PRIQ<PPPI> Q;
int nx, ny, cx, cy;
memset(vis, 0, sizeof(vis));
while (!Q.empty()) Q.pop();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] != 'S') continue;
for (int dx = -2; dx <= 2; dx++) {
nx = i + dx;
for (int dy = 1; dy <= 3; dy++) {
ny = j + dy;
if (inmat(nx, ny) && dis(i, j, nx, ny) <= 3 && mat[nx][ny] != 'X' && !vis[i][j][nx][ny]) {
if (isdigit(mat[nx][ny])) Q.push(PPPI((int) '0' - mat[nx][ny], PPP(PII(i, j), PII(nx, ny))));
else Q.push(PPPI(0, PPP(PII(i, j), PII(nx, ny))));
vis[i][j][nx][ny] = true;
//                        cout << i << ' ' << j << ' ' << nx << ' ' << ny << endl;
}
ny = j - dy;
if (inmat(nx, ny) && dis(nx, ny, i, j) <= 3 && mat[nx][ny] != 'X' && !vis[nx][ny][i][j]) {
if (isdigit(mat[nx][ny])) Q.push(PPPI((int) '0' - mat[nx][ny], PPP(PII(nx, ny), PII(i, j))));
else Q.push(PPPI(0, PPP(PII(nx, ny), PII(i, j))));
vis[nx][ny][i][j] = true;
//                        cout << nx << ' ' << ny << ' ' << i << ' ' << j << endl;
}
}
}
}
}
//    cout << "find S" << endl;
while (!Q.empty()) {
PPPI cur = Q.top();
Q.pop();
int v = cur.FI, a = cur.SE.FI.FI, b = cur.SE.FI.SE, c = cur.SE.SE.FI, d = cur.SE.SE.SE;
//        cout << v << ' ' << a << ' ' << b << ' ' << c << ' ' << d << endl;
if (mat[a][b] == 'T' || mat[c][d] == 'T') return -v;
for (int dx = -2; dx <= 2; dx++) {
nx = a + dx;
cx = c + dx;
for (int dy = 1; dy <= 3; dy++) {
ny = b + dy;
if (inmat(nx, ny) && dis(a, b, nx, ny) <= 3 && mat[nx][ny] != 'X' && !vis[a][b][nx][ny]) {
if (isdigit(mat[nx][ny])) Q.push(PPPI((int) '0' - mat[nx][ny] + v, PPP(PII(a, b), PII(nx, ny))));
else Q.push(PPPI(v, PPP(PII(a, b), PII(nx, ny))));
vis[a][b][nx][ny] = true;
//                    cout << nx << ' ' << ny << endl;
}
cy = d - dy;
if (inmat(cx, cy) && dis(cx, cy, c, d) <= 3 && mat[cx][cy] != 'X' && !vis[cx][cy][c][d]) {
if (isdigit(mat[cx][cy])) Q.push(PPPI((int) '0' - mat[cx][cy] + v, PPP(PII(cx, cy), PII(c, d))));
else Q.push(PPPI(v, PPP(PII(cx, cy), PII(c, d))));
vis[cx][cy][c][d] = true;
//                    cout << cx << ' ' << cy << endl;
}
}
}
}
return -1;
}

int main() {
//    freopen("in", "r", stdin);
//    freopen("out", "w", stdout);
while (cin >> m >> n && (n || m)) {
char buf[3];
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> buf, mat[i][j] = buf[0];
cout << work() << endl;
}
return 0;
}

——written by Lyon

1. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。