• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            superman

            聚精會神搞建設 一心一意謀發展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            Section 3.3 - Camelot

            Posted on 2009-06-04 13:50 superman 閱讀(240) 評論(0)  編輯 收藏 引用 所屬分類: USACO
              1 #include <queue>
              2 #include <iostream>
              3 
              4 using namespace std;
              5 
              6 struct point {
              7     int x, y;
              8     point operator+(const point &p) const {
              9         point np = { x + p.x, y + p.y };
             10         return np;
             11     }
             12 }   ;
             13 
             14 int r, c, knightsNum;
             15 point king, knights[30 * 26];
             16 
             17 const point kinghtDir[8= {
             18     {-2+1}, {-1+2}, {+1+2}, {+2+1},
             19     {+2-1}, {+1-2}, {-1-2}, {-2-1}
             20 }   ;
             21 
             22 inline bool inside(const point &p) {
             23     return p.x >= 0 && p.x < r && p.y >= 0 && p.y < c;
             24 }
             25 
             26 int dist[30][26][30][26];
             27 void spfa(const point &s)
             28 {
             29     for (int i = 0; i < r; i++)
             30     for (int j = 0; j < c; j++)
             31         dist[s.x][s.y][i][j] = INT_MAX;
             32     dist[s.x][s.y][s.x][s.y] = 0;
             33 
             34     queue<point> q;
             35     q.push(s);
             36 
             37     point cp;   //current point
             38     point np;   //next point
             39     while (q.empty() == false)
             40     {
             41         cp = q.front(); q.pop();
             42         for (int i = 0; i < 8; i++)
             43         {
             44             np = cp + kinghtDir[i];
             45             if (inside(np) && dist[s.x][s.y][cp.x][cp.y] + 1 < dist[s.x][s.y][np.x][np.y])
             46             {
             47                 dist[s.x][s.y][np.x][np.y] = dist[s.x][s.y][cp.x][cp.y] + 1;
             48                 q.push(np);
             49             }
             50         }
             51     }
             52 }
             53 
             54 int ans = INT_MAX;
             55 void gather(int tx, int ty)
             56 {
             57     int sum = 0;
             58     for (int i = 0; i < knightsNum; i++)
             59         sum += dist[knights[i].x][knights[i].y][tx][ty];
             60 
             61     if (sum > ans)
             62         return;
             63 
             64     for (int i = max(0, king.x - 2); i <= min(r - 1, king.x + 2); i++)
             65     for (int j = max(0, king.y - 2); j <= min(c - 1, king.y + 2); j++)
             66     {
             67         int tmp;
             68         if (i == king.x && j == king.y)
             69             tmp = 0;
             70         else
             71         {
             72             if (abs(i - king.x) == 1 || abs(j - king.y == 1))
             73                 tmp = 1;
             74             else
             75                 tmp = 2;
             76         }
             77         for (int k = 0; k < knightsNum; k++)
             78             if (dist[knights[k].x][knights[k].y][i][j] != INT_MAX &&
             79                 dist[i][j][tx][ty] != INT_MAX)
             80             ans <?= (sum - dist[knights[k].x][knights[k].y][tx][ty]
             81                 + tmp + dist[knights[k].x][knights[k].y][i][j] + dist[i][j][tx][ty]);
             82     }
             83 }
             84 
             85 int main()
             86 {
             87     freopen("camelot.in""r", stdin);
             88     freopen("camelot.out""w", stdout);
             89 
             90     cin >> r >> c;
             91 
             92     {
             93         char a; int b;
             94         cin >> a >> b;
             95         king.y = a - 'A', king.x = b - 1;
             96         while (cin >> a >> b)
             97         {
             98             knights[knightsNum].y = a - 'A';
             99             knights[knightsNum].x = b - 1;
            100             knightsNum++;
            101         }
            102     }
            103 
            104     if (knightsNum == 0)
            105     {
            106         cout << 0 << endl;
            107         return 0;
            108     }
            109 
            110     for (int i = 0; i < r; i++)
            111     for (int j = 0; j < c; j++)
            112     {
            113         point cp = { i, j };
            114         spfa(cp);
            115     }
            116 
            117     for (int i = 0; i < r; i++)
            118     for (int j = 0; j < c; j++)
            119         gather(i, j);
            120 
            121     cout << ans << endl;
            122 
            123     return 0;
            124 }
            125 
            激情五月综合综合久久69| 国产亚洲精久久久久久无码77777 国产亚洲精品久久久久秋霞 | 亚洲欧洲久久av| 久久免费看黄a级毛片| 久久综合国产乱子伦精品免费| 国产精品美女久久久久久2018| 青青草国产成人久久91网| 亚洲欧洲精品成人久久曰影片| 久久久久久亚洲AV无码专区| 超级碰久久免费公开视频| 亚洲综合伊人久久综合| 国产精品一区二区久久精品无码| 久久精品国产99久久久古代 | 亚洲欧美成人久久综合中文网| 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 亚洲国产精品狼友中文久久久 | 久久天天日天天操综合伊人av| 热re99久久6国产精品免费| 久久97久久97精品免视看| 亚洲午夜无码久久久久| 久久亚洲欧洲国产综合| 精品久久久久久久| 久久香蕉超碰97国产精品| 日韩一区二区三区视频久久| 久久久中文字幕| 久久久久亚洲AV无码永不| 欧美日韩久久中文字幕| 欧美亚洲另类久久综合婷婷 | 久久久久亚洲精品中文字幕| 国产999精品久久久久久| 国产成人久久激情91| 亚洲日韩中文无码久久| 久久久久亚洲AV片无码下载蜜桃 | 久久久中文字幕日本| 色综合合久久天天综合绕视看| 久久婷婷五月综合97色一本一本| 久久国产AVJUST麻豆| 久久九九久精品国产免费直播| 亚洲国产高清精品线久久| 精品久久久久成人码免费动漫 | 久久精品人人做人人爽电影|