UVa 10285 Longest Run on a Snowboard

　　记忆化搜索，完事。。。
Code

  1 /**
  2  * UVa
  3  * Problem#10285
  4  * Accepted
  5  * Time:0ms
  6  */
  7 #include<iostream>
  8 #include<fstream> 
  9 #include<sstream>
 10 #include<algorithm>
 11 #include<cstdio>
 12 #include<cstring>
 13 #include<cstdlib>
 14 #include<cctype>
 15 #include<cmath>
 16 #include<ctime>
 17 #include<map>
 18 #include<stack>
 19 #include<set>
 20 #include<queue>
 21 #include<vector>
 22 #ifndef WIN32
 23 #define AUTO "%lld"
 24 #else
 25 #define AUTO "%I64d"
 26 #endif
 27 using namespace std;
 28 typedef bool boolean;
 29 #define inf 0xfffffff
 30 #define smin(a, b) (a) = min((a), (b))
 31 #define smax(a, b) (a) = max((a), (b))
 32 template<typename T>
 33 inline boolean readInteger(T& u) {
 34     char x;
 35     int aFlag = 1;
 36     while(!isdigit((x = getchar())) && x != '-' && x != -1);
 37     if(x == -1)    {
 38         ungetc(x, stdin);
 39         return false;
 40     }
 41     if(x == '-') {
 42         aFlag = -1;
 43         x = getchar();
 44     }
 45     for(u = x - '0'; isdigit((x = getchar())); u = u * 10 + x - '0');
 46     u *= aFlag;
 47     ungetc(x, stdin);
 48     return true;
 49 }
 50 
 51 template<typename T>class Matrix{
 52     public:
 53         T *p;
 54         int lines;
 55         int rows;
 56         Matrix():p(NULL){    }
 57         Matrix(int rows, int lines):lines(lines), rows(rows){
 58             p = new T[(lines * rows)];
 59         }
 60         T* operator [](int pos){
 61             return (p + pos * lines);
 62         }
 63 };
 64 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows)
 65 
 66 int T;
 67 char name[100];
 68 int n, m;
 69 Matrix<int> h;
 70 
 71 inline void init() {
 72     scanf("%s", name);
 73     readInteger(n);
 74     readInteger(m);
 75     h = Matrix<int>(n, m);
 76     for(int i = 0; i < n; i++) {
 77         for(int j = 0; j < m; j++) {
 78             readInteger(h[i][j]);
 79         }
 80     }
 81 }
 82 
 83 const int mov[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};
 84 boolean isExceeded(int x, int y) {
 85     if(x < 0 || x >= n)    return true;
 86     if(y < 0 || y >= m)    return true;
 87     return false;
 88 }
 89 
 90 Matrix<int> f;
 91 int dfs(int x, int y) {
 92     if(f[x][y])    return f[x][y];
 93     for(int i = 0, ret; i < 4; i++) {
 94         int x0 = x + mov[0][i], y0 = y + mov[1][i];
 95         if(isExceeded(x0, y0))    continue;
 96         if(h[x0][y0] >= h[x][y])    continue;
 97         ret = dfs(x0, y0);
 98         smax(f[x][y], ret + 1);
 99     }
100     if(f[x][y] == 0)    f[x][y] = 1;
101     return f[x][y];
102 }
103 
104 inline void solve() {
105     f = Matrix<int>(n, m);
106     matset(f, 0, sizeof(int));
107     int res = 0;
108     for(int i = 0; i < n; i++) {
109         for(int j = 0; j < m; j++) {
110             if(f[i][j] == 0)
111                 dfs(i, j);
112             smax(res, f[i][j]);
113         }
114     }
115     printf("%s: %d
", name, res);
116     delete[] f.p;
117     delete[] h.p;
118 }
119 
120 int main() {
121     readInteger(T);
122     while(T--) {
123         init();
124         solve();
125     }
126     return 0;
127 }