posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          PKU 1008 滑雪

          Posted on 2007-05-19 22:19 ZelluX 閱讀(380) 評(píng)論(0)  編輯  收藏 所屬分類: Algorithm

          5.19
          第一反應(yīng)覺(jué)得是個(gè)簡(jiǎn)單的BFS,從最高點(diǎn)開始向四周擴(kuò)展,最后找到最長(zhǎng)的路徑即可。
          結(jié)果Wrong Answer,仔細(xì)一想,才意識(shí)到并不一定是從最高點(diǎn)開始的。考慮得太不周到了。。

          5.31
          原來(lái)的程序找不到了。。。重新寫了一遍,居然寫好提交就AC了,恩。這幾天進(jìn)步挺大哈

          #include <iostream>
          #include 
          <fstream>
          #include 
          <algorithm>
          #include 
          <vector>

          using namespace std;

          const int MAX_HEIGHT = 10000;
          const int MAX_ROWS = 100;
          const int dx[] = {00-11};
          const int dy[] = {1-100};

          struct Point {
              
          int x;
              
          int y;
              
          int height;
          }
          ;

          bool comparePoints(const Point& p1, const Point& p2);
          int main() {
              
          //ifstream fin("pku1088.in");
              int c, r;
              
          int i, j;
              cin 
          >> r >> c;
              
          int h[MAX_ROWS + 2][MAX_ROWS + 2];
              
          int count = 0;
              vector
          <Point> points;
              
          for (i = 1; i <= r; i++{
                  
          for (j = 1; j <= c; j++{
                      cin 
          >> h[i][j];
                      Point temp;
                      temp.x 
          = i;
                      temp.y 
          = j;
                      temp.height 
          = h[i][j];
                      points.push_back(temp);
                  }

              }


              sort(points.begin(), points.end(), comparePoints);
              
              
          for (i = 0; i <= c; i++{
                  h[
          0][i] = MAX_HEIGHT + 1;
                  h[r 
          + 1][i] = MAX_HEIGHT + 1;
              }

              
          for (i = 0; i <= r; i++{
                  h[i][
          0= MAX_HEIGHT + 1;
                  h[i][c 
          + 1= MAX_HEIGHT + 1;
              }


              
          int f[MAX_ROWS + 1][MAX_ROWS + 1];
              
          for (i = 1; i <= r; i++{
                  
          for (int j = 1; j <= c; j++{
                      f[i][j] 
          = 1;
                  }

              }

              
              vector
          <Point>::iterator iter;
              
          for (iter = points.begin(); iter != points.end(); iter++{
                  
          for (i = 0; i < 4; i++{
                      
          int nx = iter->+ dx[i];
                      
          int ny = iter->+ dy[i];
                      
          if (iter->height > h[nx][ny]) {
                          
          if (f[iter->x][iter->y] + 1 > f[nx][ny]) {
                              f[nx][ny] 
          = f[iter->x][iter->y] + 1;
                          }

                      }

                  }

              }


              
          int best = 0;
              
          for (i = 1; i <= r; i++{
                  
          for (j = 1; j <= c; j++{
                      
          if (f[i][j] > best) {
                          best 
          = f[i][j];
                      }

                  }

              }

              cout 
          << best << endl;
              
          return 0;
          }


          bool comparePoints(const Point& p1, const Point& p2) {
              
          return (p1.height > p2.height);
          }
          主站蜘蛛池模板: 唐河县| 芜湖市| 周至县| 天水市| 张家口市| 抚顺县| 临城县| 庆城县| 南丰县| 合山市| 东阳市| 古丈县| 赞皇县| 崇左市| 阳高县| 黄大仙区| 台北县| 碌曲县| 城市| 望都县| 太仓市| 周口市| 平阳县| 金湖县| 珲春市| 江山市| 洛扎县| 平乐县| 胶南市| 齐齐哈尔市| 乐都县| 兴国县| 南涧| 祁阳县| 磐石市| 石林| 竹山县| 隆尧县| 河北区| 开平市| 寿阳县|