ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 628 Div2 Easy : BishopMove

解法・感想など


長ったらしく探索させているが、そんなことしなくてよい。

斜め移動しかできないことが分かっているので、市松模様の同じ色にコマが置かれているかどうかが分かれば良い。
同じ色に置いてあれば最大でも2回以内に目的地に到達できる。

  • -

215.5 / 250

ソースコード

class BishopMove {
public:
  
  int minCost[8][8];

  void rec(int r, int c, int count) {
    minCost[r][c] = count;
    
    for(int i = -1; i <= 1; i += 2) {
      for(int j = -1; j <= 1; j += 2) {
        for(int k = 0; k < 8; k++) {
          int nr = r + i * k;
          int nc = c + j * k;
          if(!(0 <= nr && nr < 8 && 0 <= nc && nc < 8)) continue;
          if(minCost[nr][nc] > minCost[r][c] + 1) {
            rec(nr, nc, count + 1);
          }
        }
      }
    }
  }

  int howManyMoves(int r1, int c1, int r2, int c2) {
    rep(i, 8) rep(j, 8) minCost[i][j] = (1 << 30);
    
    rec(r1, c1, 0);
    
    int ans = minCost[r2][c2];
    if(ans == (1 << 30)) ans = -1;
    
    return ans;
  }
};