Algorithm

 Problem Statement for CornersGame

problem link- https://community.topcoder.com/stat?c=problem_statement&pm=6475&rd=9988

Problem Statement
    

This problem contains an image that can be viewed in the applet.

A player has four draughts which are placed in the bottom right corner of a 6 x 6 chessboard. The draughts are arranged in a square with 2 rows and 2 columns (see picture below). Some cells on the board may contain red flags, and some may contain stones.

The player's goal is to move all the draughts to the top left corner and arrange them in a square using a minimal number of moves. The draughts are indistinguishable, so their order in the final position doesn't matter. The target cells are guaranteed to be free. There are two kinds of moves that can be made by a draught. The first is to move to any vertically or horizontally adjacent free cell. The second is to jump over a single vertically or horizontally adjacent draught or stone into a free cell. The player can never move a draught into a cell that contains a flag, stone or other draught and he can never jump over a flag or an empty space.

You will be given a String[] board where each element represents a single row of the chessboard. The rows are given from top to bottom, and each row is given from left to right. '.' represents a free cell, 'r' represents a cell with a red flag, and 's' represents a cell with a stone. Return the minimal number of moves necessary to reach the goal, or -1 if it is impossible.
 

Definition
    
Class: CornersGame
Method: countMoves
Parameters: String[]
Returns: int
Method signature: int countMoves(String[] board)
(be sure your method is public)
    
 
 

Constraints
- board will contain exactly 6 elements.
- Each element of board will contain exactly 6 characters.
- Each element of board will contain only the characters 'r', 's', and '.'.
- board will contain '.' characters at the initial and desired final positions of the draughts.
 

Examples
0)  
     
{"......", 
 "......",
 "......",
 "......",
 "......",
 "......"}
 
Returns: 16
 
1)  
     
{".....s",
 "..s.r.",
 "r.....",
 ".srs..",
 "..r...",
 "......"}
 
Returns: 19
The board shown on the picture above.
2)  
     
{"......",
 "......",
 "....ss",
 "....ss",
 "...r..",
 "...r.."}
 
Returns: -1
We can not make any move.
3)  
     
{"...s.r",
 "..r.s.",
 "rr.s..",
 "..s.rr",
 "s.rr..",
 ".s.s.."}
 
Returns: 54

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

struct node {
  int x[4], y[4];
  node() {}
  node(int x0, int x1, int x2, int x3,
    int y0, int y1, int y2, int y3) {
    x[0] = x0, x[1] = x1, x[2] = x2, x[3] = x3;
    y[0] = y0, y[1] = y1, y[2] = y2, y[3] = y3;
  }
};

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int endx[] = { 0, 0, 1, 1 };
int endy[] = { 1, 0, 1, 0 };
int vis[6][6][6][6][6][6][6][6];
queue <node> q;

bool free(node fr, int nx, int ny) {
  for(int i = 0; i  < 4; ++i)
    if(fr.x[i] == nx && fr.y[i] == ny)
      return false;
  return true;
}

bool end(node fr) {
  int cnt = 0;
  for(int i = 0; i  < 4; ++i)
    for(int j = 0; j  < 4; ++j)
      if(fr.x[j] == endx[i] && fr.y[j] == endy[i]) {
        ++cnt;
        break;
      }
  return cnt == 4;
}

class CornersGame {
public:
  int countMoves(vector<string> board) {
    q.push(node(4, 4, 5, 5, 4, 5, 4, 5));
    vis[4][4][5][5][4][5][4][5] = true;

    int cost = 0;
    while(!q.empty()) {
      int size = q.size();
      
      while(size-- != 0) {
        node fr = q.front();
        q.pop();
        
        if(end(fr))
          return cost;
        
        for(int i = 0; i < 4; ++i) {
          int curx = fr.x[i], cury = fr.y[i];
          
          for(int j = 0; j  < 4; ++j) {
            int nx = curx + dx[j];
            int ny = cury + dy[j];
            
            if(nx  < 0 || nx >= 6 || ny  < 0 || ny >= 6 || board[nx][ny] == 'r')
              continue;
            
            if(board[nx][ny] == '.' && free(fr, nx, ny)) {
              fr.x[i] += dx[j], fr.y[i] += dy[j];
              if(vis[fr.x[0]][fr.x[1]][fr.x[2]][fr.x[3]][fr.y[0]][fr.y[1]][fr.y[2]][fr.y[3]]) {
                fr.x[i] -= dx[j], fr.y[i] -= dy[j];
                continue;
              }
              q.push(fr);
              vis[fr.x[0]][fr.x[1]][fr.x[2]][fr.x[3]][fr.y[0]][fr.y[1]][fr.y[2]][fr.y[3]] = true;
              fr.x[i] -= dx[j], fr.y[i] -= dy[j];
            } else if(board[nx][ny] == 's' || !free(fr, nx, ny)) {
              int tmpx = curx + dx[j] * 2;
              int tmpy = cury + dy[j] * 2;
              if(tmpx  < 0 || tmpx >= 6 || tmpy  < 0 || tmpy >= 6 || board[tmpx][tmpy] == 'r')
                continue;
              
              if(board[tmpx][tmpy] != 's' && free(fr, tmpx, tmpy)) {
                fr.x[i] += dx[j] * 2, fr.y[i] += dy[j] * 2;
                if(vis[fr.x[0]][fr.x[1]][fr.x[2]][fr.x[3]][fr.y[0]][fr.y[1]][fr.y[2]][fr.y[3]]) {
                  fr.x[i] -= dx[j] * 2, fr.y[i] -= dy[j] * 2;
                  continue;
                }
                q.push(fr);
                vis[fr.x[0]][fr.x[1]][fr.x[2]][fr.x[3]][fr.y[0]][fr.y[1]][fr.y[2]][fr.y[3]] = true;
                fr.x[i] -= dx[j] * 2, fr.y[i] -= dy[j] * 2;
              }
            }
          }
        }
      }
      
      ++cost;
    }
    
    return -1;
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{"......", "......", "......", "......", "......", "......"}

Output

x
–
+
cmd
16
Advertisements

Demonstration

TopCoder Solution SRM308-D1-500 Problem Statement for CornersGame C,C++, Java, Js and Python ,SRM308-D1-500,TopCoder Solution