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

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 8 using namespace std; 9 10 typedef pair
            
              PII;11 typedef pair
             
               PPP;12 typedef pair
              
                PPPI;13 14 #define FI first15 #define SE second16 #define PRIQ priority_queue17 18 const int R = 66;19 const int C = 33;20 char mat[R][C];21 bool vis[R][C][R][C];22 int n, m;23 24 inline int dis(int a, int b, int c, int d) { return abs(a - c) + abs(b - d);}25 inline bool inmat(int a, int b) { return 0 <= a && a < n && 0 <= b && b < m;}26 27 int work() {28 PRIQ
               
                 Q;29 int nx, ny, cx, cy;30 memset(vis, 0, sizeof(vis));31 while (!Q.empty()) Q.pop();32 for (int i = 0; i < n; i++) {33 for (int j = 0; j < m; j++) {34 if (mat[i][j] != 'S') continue;35 for (int dx = -2; dx <= 2; dx++) {36 nx = i + dx;37 for (int dy = 1; dy <= 3; dy++) {38 ny = j + dy;39 if (inmat(nx, ny) && dis(i, j, nx, ny) <= 3 && mat[nx][ny] != 'X' && !vis[i][j][nx][ny]) {40 if (isdigit(mat[nx][ny])) Q.push(PPPI((int) '0' - mat[nx][ny], PPP(PII(i, j), PII(nx, ny))));41 else Q.push(PPPI(0, PPP(PII(i, j), PII(nx, ny))));42 vis[i][j][nx][ny] = true;43 // cout << i << ' ' << j << ' ' << nx << ' ' << ny << endl;44 }45 ny = j - dy;46 if (inmat(nx, ny) && dis(nx, ny, i, j) <= 3 && mat[nx][ny] != 'X' && !vis[nx][ny][i][j]) {47 if (isdigit(mat[nx][ny])) Q.push(PPPI((int) '0' - mat[nx][ny], PPP(PII(nx, ny), PII(i, j))));48 else Q.push(PPPI(0, PPP(PII(nx, ny), PII(i, j))));49 vis[nx][ny][i][j] = true;50 // cout << nx << ' ' << ny << ' ' << i << ' ' << j << endl;51 }52 }53 }54 }55 }56 // cout << "find S" << endl;57 while (!Q.empty()) {58 PPPI cur = Q.top();59 Q.pop();60 int v = cur.FI, a = cur.SE.FI.FI, b = cur.SE.FI.SE, c = cur.SE.SE.FI, d = cur.SE.SE.SE;61 // cout << v << ' ' << a << ' ' << b << ' ' << c << ' ' << d << endl;62 if (mat[a][b] == 'T' || mat[c][d] == 'T') return -v;63 for (int dx = -2; dx <= 2; dx++) {64 nx = a + dx;65 cx = c + dx;66 for (int dy = 1; dy <= 3; dy++) {67 ny = b + dy;68 if (inmat(nx, ny) && dis(a, b, nx, ny) <= 3 && mat[nx][ny] != 'X' && !vis[a][b][nx][ny]) {69 if (isdigit(mat[nx][ny])) Q.push(PPPI((int) '0' - mat[nx][ny] + v, PPP(PII(a, b), PII(nx, ny))));70 else Q.push(PPPI(v, PPP(PII(a, b), PII(nx, ny))));71 vis[a][b][nx][ny] = true;72 // cout << nx << ' ' << ny << endl;73 }74 cy = d - dy;75 if (inmat(cx, cy) && dis(cx, cy, c, d) <= 3 && mat[cx][cy] != 'X' && !vis[cx][cy][c][d]) {76 if (isdigit(mat[cx][cy])) Q.push(PPPI((int) '0' - mat[cx][cy] + v, PPP(PII(cx, cy), PII(c, d))));77 else Q.push(PPPI(v, PPP(PII(cx, cy), PII(c, d))));78 vis[cx][cy][c][d] = true;79 // cout << cx << ' ' << cy << endl;80 }81 }82 }83 }84 return -1;85 }86 87 int main() {88 // freopen("in", "r", stdin);89 // freopen("out", "w", stdout);90 while (cin >> m >> n && (n || m)) {91 char buf[3];92 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> buf, mat[i][j] = buf[0];93 cout << work() << endl;94 }95 return 0;96 }
               
              
             
            
           
          
         
        
       
      

 

——written by Lyon