naoya_t@topcoder

SRM207 Div2 Hard: CaptureThemAll

過去問, 練習, Tutorials | 21:05 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

Problem hints: At first sight this may seem like dynamic programming or backtracking. But as always, take a look into the text of the statement. After a while you should observe the following things:

• A table is given.
• The knight can jump from one cell to some of its neighbors.
• The cost of passing from a cell to another is always 1 (just one jump).
• You need to find the minimum number of steps (jumps).

Given this information we can see that the problem can be easily solved by the help of BFS. Don't get confused by the fact that connected points are represented by unconnected cells. Think of cells as points in a graph, or states (whatever you want) - and in order to pass from one point to another, the knight should be able to jump from the first to the second point.

Notice again that the most revealing hint about the BFS solution is the cost of 1 for any jump.

「ジャンプのコストが全て１」→BFSで解けるよというあからさまなヒント

• 特に難しくない
• 駒の位置の表現をintに詰めるかpair<int,int>にするかとか迷った
• 答え合わないなと思ってたら８方位のうち６方位しか行かないバグがあった
• 430.94points (49'26''...遅い!!!), Passed System Test

#define rep(var,n)  for(int var=0;var<(n);var++)

int ds[8][2] = { {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1} };

class CaptureThemAll {
  inline int pii(int c,int r){ return (c<<3)|r; }
  inline int piic(int p){ return p>>3; }
  inline int piir(int p){ return p&7; }
 
  int cell(string cr){
    int c = (cr[0] - 'a') & 0x07;
    int r = (cr[1] - '1') & 0x07;
    return pii(c,r);
  }

  int chase(int p0,int p1){
    int board[8][8];
    rep(c,8) rep(r,8) board[c][r]=INT_MAX;
    int p0c=piic(p0),p0r=piir(p0), p1c=piic(p1),p1r=piir(p1);
    board[p0c][p0r]=0;
    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0,p0));
    while(!pq.empty()){
      int sc=-pq.top().first, at=pq.top().second;
      pq.pop();
      int atc=piic(at),atr=piir(at);
      rep(i,8){
        int c_=atc+ds[i][0], r_=atr+ds[i][1];
        if(c_<0 || 7<c_ || r_<0 || 7<r_) continue;
        int sc_=sc+1;
        if (c_==p1c && r_==p1r) return sc_;
        if (board[c_][r_]>sc_) {
          board[c_][r_]=sc_;
          pq.push(make_pair(-sc_,pii(c_,r_)));
        }
      }
    }
    return 64;
  }
 public:
  int fastKnight(string knight, string rook, string queen) {
    int kn=cell(knight), ro=cell(rook), qu=cell(queen);
    return min( chase(kn,ro)+chase(ro,qu), chase(kn,qu)+chase(qu,ro) );
  }
};

• デバッグ用のプリティプリンタ込みでソース晒すよ

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
// BEGIN CUT HERE
#include "cout.h"
// END CUT HERE
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define forr(var,from,to) for(int var=(from);var<=(to);var++) 
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))

int ds[8][2] = { {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1} };

class CaptureThemAll {
  inline int pii(int c,int r){ return (c<<3)|r; }
  inline int piic(int p){ return p>>3; }
  inline int piir(int p){ return p&7; }
  
  int cell(string cr){
    int c = (cr[0] - 'a') & 0x07;
    int r = (cr[1] - '1') & 0x07;
    return pii(c,r);
  }
// BEGIN CUT HERE
  void cellpp(int cell){
    int c=piic(cell), r=piir(cell);
    printf("%c%c (%d,%d)", ('a'+c),('1'+r),c,r);
  }
  void pp(int kn,int ro,int qu){
    cout << endl << "  a b c d e f g h " << endl;
    cout << " +-+-+-+-+-+-+-+-+" << endl;
    rep(r,8){
      cout << (1+r) << "|";
      rep(c,8){
        int cr=pii(c,r);
        int ch=((kn==cr)?4:0)+((ro==cr)?2:0)+((qu==cr)?1:0);
        switch(ch){
          case 0: cout << " |"; break;
          case 1: cout << "Q|"; break;
          case 2: cout << "R|"; break;
          case 3: cout << "RQ"; break;
          case 4: cout << "K|"; break;
          case 5: cout << "KQ"; break;
          case 6: cout << "KR"; break;
          case 7: cout << "*|"; break;
        }
      }
      cout << endl << " +-+-+-+-+-+-+-+-+" << endl;
    }
  }
  void boardpp(int board[][8]){
    cout << "    a  b  c  d  e  f  g  h " << endl;
    cout << "  +--+--+--+--+--+--+--+--+" << endl;
    rep(r,8){
      cout << (1+r) << " |";
      rep(c,8){
        int sc=board[c][r];
        if(sc>64) cout << "  |";
        else printf("%2d|",sc);
      }
      cout << endl << "  +--+--+--+--+--+--+--+--+" << endl;
    }
  }
// END CUT HERE

  int chase(int p0,int p1){
// BEGIN CUT HERE
    cout << "chase: "; cellpp(p0); cout << " => "; cellpp(p1); cout << endl;
// END CUT HERE
    int board[8][8];
    rep(c,8) rep(r,8) board[c][r]=INT_MAX;
    int p0c=piic(p0),p0r=piir(p0), p1c=piic(p1),p1r=piir(p1);
    board[p0c][p0r]=0;
    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0,p0));
    while(!pq.empty()){
      int sc=-pq.top().first, at=pq.top().second;
      pq.pop();
      int atc=piic(at),atr=piir(at);
      rep(i,8){
        int c_=atc+ds[i][0], r_=atr+ds[i][1];
        if(c_<0 || 7<c_ || r_<0 || 7<r_) continue;
        int sc_=sc+1;
        if (c_==p1c && r_==p1r) {
// BEGIN CUT HERE
          board[c_][r_]=sc_;
          boardpp(board); cout << "sc=" << sc_ << endl;
// END CUT HERE
          return sc_;
        }
        if (board[c_][r_]>sc_) {
          board[c_][r_]=sc_;
          pq.push(make_pair(-sc_,pii(c_,r_)));
        }
      }
    }
    return 64;
  }
 public:
  int fastKnight(string knight, string rook, string queen) {
    int kn=cell(knight), ro=cell(rook), qu=cell(queen);
// BEGIN CUT HERE
    /*
    cout << "knight: "; cellpp(kn); cout << endl;
    cout << "  rook: "; cellpp(ro); cout << endl;
    cout << " queen: "; cellpp(qu); cout << endl;
    */
    pp(kn,ro,qu);
// END CUT HERE
    return min( chase(kn,ro)+chase(ro,qu), chase(kn,qu)+chase(qu,ro) );
  }
};