usaco 3_3_3 camelot 题解_leokan的blog.mht

美国USACO题库源程序

            }
            if (x < ncol-2) {
                if (dist[x+2][y+1][kflag] > d+1) {
                    dist[x+2][y+1][kflag] =3D d+1;
                    f =3D 1;
                }
            }
        if (y < nrow-2) {
            if (x > 0)
                if (dist[x-1][y+2][kflag] > d+1) {
                    dist[x-1][y+2][kflag] =3D d+1;
                    f =3D 1;
                }
            if (x < ncol-1)
                if (dist[x+1][y+2][kflag] > d+1) {
                    dist[x+1][y+2][kflag] =3D d+1;
                    f =3D 1;
                }
        }
    }

/* also check the 'pick up king here' move */
    if (kflag =3D=3D 0 && dist[x][y][1] > d + kdist[x][y]) {
        dist[x][y][1] =3D d + kdist[x][y];
        if (kdist[x][y] > f) f =3D kdist[x][y];
    }
    return f; /* 1 if simple knight move made, 0 if no new move found */
}

void calc_dist(int col, int row) {
    int lv, lv2; /* loop variables */
    int d;  /* current distance being checked */
    int max;   /* maximum finite distance found so far */
    int f;   /* temporary variable (returned value from do_step */

/* initiate all positions to be infinite distance away */
    for (lv =3D 0; lv < ncol; lv++)
        for (lv2 =3D 0; lv2 < nrow; lv2++)
            dist[lv][lv2][0] =3D dist[lv][lv2][1] =3D MAXN;

/* starting location is zero w/o king, kdist[col][row] with king */
    dist[col][row][0] =3D 0;
    max =3D dist[col][row][1] =3D kdist[col][row];

    for (d =3D 0; d <=3D max; d++) { /* for each distance away */
        for (lv =3D 0; lv < ncol; lv++)
            for (lv2 =3D 0; lv2 < nrow; lv2++) {
    /* for each position that distance away */
                if (dist[lv][lv2][0] =3D=3D d) {
     /* update with moves through this square */
                    f =3D do_step(lv, lv2, 0);
                    if (d + f > max)     /* update max if necessary =
*/
   max =3D d + f;
                 }

                 if (dist[lv][lv2][1] =3D=3D d) {
   /* same as above, except this time knight has king */
                     f =3D do_step(lv, lv2, 1);
                     if (d + f > max) max =3D d + f;
                 }
            }
    }
}

int main(int argc, char **argv) {
    FILE *fout, *fin;
    char t[10];
    int pr, pc;
    int lv, lv2;
    int i, j;

    if ((fin =3D fopen("camelot.in", "r")) =3D=3D NULL) {
        perror ("fopen fin");
        exit(1);
    }
    if ((fout =3D fopen("camelot.out", "w")) =3D=3D NULL) {
        perror ("fopen fout");
        exit(1);
    }

    fscanf (fin, "%d %d", &nrow, &ncol);
    fscanf (fin, "%s %d", t, &pr);
    pc =3D t[0] - 'A';
    pr--;

  /* Calculate cost of moving king from starting position to
   * each board position.  This is just the taxi-cab distance */
   for (lv =3D 0; lv < ncol; lv++)
       for (lv2 =3D 0; lv2 < nrow; lv2++) {
           i =3D abs(pc-lv);
           j =3D abs(pr-lv2);
           if (i < j) i =3D j;
           kingcost[lv][lv2] =3D kdist[lv][lv2] =3D i;
       }

    while (fscanf (fin, "%s %d", t, &pr) =3D=3D 2) { /* for all =
knights */
        pc =3D t[0] - 'A';
        pr--;

        /* calculate distances */
        calc_dist(pc, pr);

        for (lv =3D 0; lv < ncol; lv++)
            for (lv2 =3D 0; lv2 < nrow; lv2++) {
                /* to collect here, we must also move knight here */
                cost[lv][lv2] +=3D dist[lv][lv2][0];

         /* check to see if it's cheaper for the new knight to
            pick the king up instead of whoever is doing it now */
         if (dist[lv][lv2][1] - dist[lv][lv2][0] < kingcost[lv][lv2]) =
{
             kingcost[lv][lv2] =3D dist[lv][lv2][1] - dist[lv][lv2][0];
         }
            }
    }
    /* find best square to collect in */
    pc =3D cost[0][0] + kingcost[0][0];

    for (lv =3D 0; lv < ncol; lv++)
        for (lv2 =3D 0; lv2 < nrow; lv2++)
            if (cost[lv][lv2] + kingcost[lv][lv2] < pc) /* better =
square? */
                pc =3D cost[lv][lv2] + kingcost[lv][lv2];=20
  fprintf (fout, "%i\n", pc);
  return 0;
}
</STRONG></PRE>
      <P><STRONG><EM>Iran's Mohammedreza Jahedbozorgan likes this =
cleaner=20
      solution:</EM> </STRONG></P><PRE><STRONG>#include &lt;iostream&gt;
#include &lt;fstream&gt;

using std::ifstream;
using std::ofstream;
using std::endl;
using std::cerr;

const short MAXROWS =3D 40,
            MAXCOLS =3D 26,
            INFINITY =3D 32767;

struct position {
    short r;
    short c;
} knightsPos[MAXROWS * MAXCOLS], kingPos;

struct path {
    short r;
    short c;
    short distance;
};

int moves2AggregatePoint();
void buildKnightsDistances(const short, const short);
void buildKingDistance(const short, const short, const short);

short knightMoveR[8] =3D {-2, -2, -1, -1, 1, 1, 2, 2},
      knightMoveC[8] =3D {-1, 1, -2, 2, -2, 2, -1, 1},
      kingMoveR[8] =3D {-1, -1, -1, 0, 0, 1, 1, 1},
      kingMoveC[8] =3D {-1, 0, 1, -1, 1, -1, 0, 1},
      rows, cols, knightCount =3D 0,
      kingDistance[MAXROWS][MAXCOLS],=20
      knightsDistances[MAXROWS][MAXCOLS][MAXROWS][MAXCOLS];

int main() {
    char ch;
    short r, c, r2, c2;

    ifstream fin("camelot.in");
    fin &gt;&gt;rows &gt;&gt;cols;
    fin &gt;&gt; ch &gt;&gt; kingPos.r;
    kingPos.r--;
    kingPos.c =3D ch - 'A';
    while (fin &gt;&gt;ch) {
        knightsPos[knightCount].c =3D ch - 'A';
        fin &gt;&gt;knightsPos[knightCount].r;
        knightsPos[knightCount++].r--;
    }
    fin.close();

    ofstream fout("camelot.out");
    if (knightCount =3D=3D 0) fout &lt;&lt;'0' &lt;&lt;endl;
    else {
        for (r =3D 0; r &lt; rows; r++)
            for (c =3D 0; c &lt; cols; c++)
                kingDistance[r][c] =3D INFINITY;
        buildKingDistance (kingPos.r, kingPos.c, 0);

        for (r =3D 0; r &lt; rows; r++)
            for (c =3D 0; c &lt; cols; c++)    =20
                for (r2 =3D 0; r2 &lt; rows; r2++)
                    for (c2 =3D 0; c2 &lt; cols; c2++)
                        knightsDistances[r][c][r2][c2] =3D INFINITY;
         for (r =3D 0; r &lt; rows; r++)
             for (c =3D 0; c &lt; cols; c++)    =20
                 buildKnightsDistances(r, c);
        fout &lt;&lt;moves2AggregatePoint() &lt;&lt;endl;
    }
    fout.close();
    return 0;
}

void buildKingDistance(const short r, const short c, const short soFar) =
{
    short a;
    kingDistance[r][c] =3D soFar;
    for (a =3D 0; a &lt; 8; a++)
        if (r + kingMoveR[a] &gt;=3D 0 &amp;&amp; r + kingMoveR[a] &lt; =
rows &amp;&amp;
  c + kingMoveC[a] &gt;=3D 0 &amp;&amp; c + kingMoveC[a] &lt; cols =
&amp;&amp;
                kingDistance[r + kingMoveR[a]][c + kingMoveC[a]] &gt; =
soFar + 1)
            buildKingDistance(r + kingMoveR[a], c + kingMoveC[a], soFar =
+ 1);
}

void buildKnightsDistances(const short a, const short b) {
    int i, queueRead =3D 0, queueWrite =3D 1;
    path me, queue[MAXROWS * MAXCOLS];

    queue[0].r =3D a;
    queue[0].c =3D b;
    queue[0].distance =3D 0;
    knightsDistances[a][b][a][b] =3D 0;

    while (queueRead &lt; queueWrite) {
        me =3D queue[queueRead++];
        for (i =3D 0; i &lt; 8; i++)
            if (me.r + knightMoveR[i] &gt;=3D 0 &amp;&amp; me.r + =
knightMoveR[i] &lt; rows &amp;&amp;
                 me.c + knightMoveC[i] &gt;=3D 0 &amp;&amp; me.c + =
knightMoveC[i] &lt; cols &amp;&amp;
                 =
knightsDistances[a][b][me.r+knightMoveR[i]][me.c+knightMoveC[i]] =3D=3D =
INFINITY) {
     queue[queueWrite].r =3D me.r + knightMoveR[i];
     queue[queueWrite].c =3D me.c + knightMoveC[i];
     queue[queueWrite++].distance =3D me.distance + 1;
            knightsDistances[a][b][me.r + knightMoveR[i]][me.c + =
knightMoveC[i]] =3D me.distance + 1;
            knightsDistances[me.r + knightMoveR[i]][me.c + =
knightMoveC[i]][a][b] =3D me.distance + 1;
 }
    }
}

int moves2AggregatePoint() {
    short r, c, i, withKing, kingNewR, kingNewC;
    int movesToRC, answer;

    answer =3D INFINITY;

    // Loop all squares and calculate minimum number of moves needed to =
gather
    // the king and all of knights there...=20
    for (r =3D 0; r &lt; rows; r++)
        for (c =3D 0; c &lt; cols; c++) {
        // First calculate minimum number of moves needed if no knights
        // picks the king up...
     movesToRC =3D 0;
     for (i =3D 0; i &lt; knightCount; i++)
  movesToRC +=3D =
knightsDistances[knightsPos[i].r][knightsPos[i].c][r][c];
     if (movesToRC + kingDistance[r][c] &lt; answer)
  answer =3D movesToRC + kingDistance[r][c];

 // Loop all knights and check if that knight picking the
 // king up yields a better answer...
        for (i =3D 0; i &lt; knightCount; i++) {
     withKing =3D INFINITY;
 // When a knight is going to pick the king up, it is not needed for =
king
        // to move more than one square.
        // Why?
        // Assume this game board: (K =3D King)
        // +-+-+-+-+-+-+-+-+
        // | | | | | | | | |
        // +-+-+-+-+-+-+-+-+
        // | |3|1|2|1|3| | |
        // +-+-+-+-+-+-+-+-+
        // | |1|0|0|0|1| | |
        // +-+-+-+-+-+-+-+-+
        // | |2|0|K|0|2| | |
        // +-+-+-+-+-+-+-+-+
        // | |1|0|0|0|1| | |
        // +-+-+-+-+-+-+-+-+
        // | |3|1|2|1|3| | |
        // +-+-+-+-+-+-+-+-+
        // | | | | | | | | |
        // +-+-+-+-+-+-+-+-+
        // | | | | | | | | |
        // +-+-+-+-+-+-+-+-+
        // The King can reach all '0' squares with minimum 1 move.
        // If he move outside the '0' area, he will reach any of =
following areas:
 // '1': King needs 2 moves to reach there, but a knight
 // located there, can reach the king with just one move.
        // '2': King needs 2 moves to reach there, and the knight
        //  located there also can reach the king with 2 moves.
 // '3': King needs 2 moves to reach there, but if the King
 //  and the knight located there each make one move can reach
 //  each other.

        for (kingNewR =3D kingPos.r - 1; kingNewR &lt;=3D kingPos.r + 1; =
kingNewR++)
            for (kingNewC =3D kingPos.c - 1; kingNewC &lt;=3D kingPos.c =
+ 1; kingNewC++)
  if (kingNewR &gt;=3D 0 &amp;&amp; kingNewC &gt;=3D 0 &amp;&amp; =
kingNewR &lt; rows &amp;&amp;
    kingNewC &lt; cols)
      if (kingDistance[kingNewR][kingNewC] +
   =
knightsDistances[knightsPos[i].r][knightsPos[i].c][kingNewR][kingNewC] +
   knightsDistances[kingNewR][kingNewC][r][c] &lt; withKing)
                 withKing =3D kingDistance[kingNewR][kingNewC] +
    =
knightsDistances[knightsPos[i].r][knightsPos[i].c][kingNewR][kingNewC] +
    knightsDistances[kingNewR][kingNewC][r][c];
                    movesToRC +=3D withKing - =
knightsDistances[knightsPos[i].r][knightsPos[i].c][r][c];
                    if (movesToRC &lt; answer) answer =3D movesToRC;
                    movesToRC -=3D withKing - =
knightsDistances[knightsPos[i].r][knightsPos[i].c][r][c];
 }
    }
    return answer;
}</STRONG></PRE>
      <P></P>
      <HR>
      </DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/5ff69f58f138cada9c820489.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 3.3.2 Shopping Offers =CC=E2=BD=E2', 'USACO =
3.3.2 Shopping Offers =
=CC=E2...','/leokan/blog/item/5e941cdf0f80fd176227984d.html'];
var post =3D [false,'','', '/leokan/blog/item/.html'];
if(pre[0] || post[0]){
	document.write('<div =
style=3D"height:5px;line-height:5px;">&nbsp;</div><div id=3D"in_nav">');
	if(pre[0]){
		document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' +  pre[2] + '</a>&nbsp;&nbsp;&nbsp;&nbsp;');
	}
	if(post[0]){
		document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =