The board game Less is played on an 8 times 8 board with randomly placed walls b

Question

The board game Less is played on an 8 times 8 board with randomly placed walls between squares. Each player aims to move their pieces to the opposite comer of the board before the others do the same. We will consider a generalized single-player version of the game, where the board has size n times n. The board is specified by a positive integer n and two (n - 1) times (n - 1) boolean arrays leftWall and bottomWall; leftWall[i][j] is true if there is a wall on the left edge of square (i, j) and false otherwise, bottomWall is analogous for walls on the bottom edge of the square. Square (0, 0) corresponds to the bottom-left, and square (n - 1,  n - 1) to the top-right. In one move, a player can move a piece one square horizontally or vertically if it is not blocked by a wall (see Figure 1, left). This is called a simple move. Give an algorithm that uses breadth-first-search to find the minimum number of simple moves to move a piece from the bottom-left comer of the board to the top-right. If the top-right comer is unreachable, your algorithm should return infinity. Why is your algorithm correct? Analyze the running time of your algorithm. A player can also move a piece one square horizontally or vertically through a wall (see Figure 1, right). This is called a wall jump,  and costs two moves. Give an algorithm that finds the minimum number of moves required to move a piece from the bottom-left comer of the board to the top-right, using both simple moves (that count as 1 move) and wall jumps (that count as 2 moves). You may use any algorithm discussed in class as a black box. Why is your algorithm correct? Analyze the running time of your algorithm. Implement your algorithm in the accompanying zip file.

Explanation / Answer

// Due to time limitation, could not write all conditions but algorithm is implemented below

// you need to add few conditions as per the questions

// Time complexity

// if we use DFS, time complexity will be O (Row x Column)

// but for BFS, time complexity will be O(Row + Column) = since we need to traverse row + column in worst case

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#define MAXSIZE 1000
#define R   50
#define C   50

int N; // no of rows and columns in matrix
int black = 0;
int count1 = 0;
int MAXANSWER = INT_MIN;
int Arr[3][51];
bool visited[R][C];

bool leftWall[R][C];
bool bottomWall[R][C];

//////////////////////// C Queue Implemetation Begins /////////////////////////

struct Point
{
   int i, j;
};

Point Q[MAXSIZE];

int front, rear, sizeOfQue;

void init_Que()
{
   front = -1;
   rear = -1;
   sizeOfQue = 0;
}

void enQue(Point data)
{
   if (sizeOfQue == MAXSIZE - 1)
   {
       return;
   }

   if (front == -1)
   {
       front = 0;
   }

   ++rear;
   Q[rear].i = data.i;
   Q[rear].j = data.j;
   sizeOfQue++;
}

Point deQue()
{
   int index = -1;

   if (front == -1 || front > rear)
   {
       return Q[index];
   }

   index = front;
   front++;
   sizeOfQue--;
   return Q[index];
}

//////////////////////// C Queue Implemetation Ends /////////////////////////

bool isSafe(int i, int j)
{
   if ((leftWall[i][j] == true) || (bottomWall[i][j] == true) && (i <N && i >= 0 && j <N && j >= 0 && visited[i][j] == false))
       return true;
   else
       return false;
}

int bfsutil(int i, int j)
{
   struct Point point;
   struct Point pointp;
   point.i = i;
   point.j = j;
   visited[i][j] = true;
   enQue(point);
   int Nodes;

   while (sizeOfQue)
   {
       count1++;
       Nodes = sizeOfQue;
       while (Nodes>0)
       {
           point = deQue();
           Nodes--;

           if (point.j == N)
               return count1;

           if (isSafe(point.i, point.j + 1) == true) //check right
           {
               visited[point.i][point.j + 1] = true;
               pointp.i = point.i;
               pointp.j = point.j + 1;
               enQue(pointp);
           }

           if (isSafe(point.i + 1, point.j) == true) // check down
           {
               visited[point.i + 1][point.j] = true;
               pointp.i = point.i + 1;
               pointp.j = point.j;
               //q.push(pointp);
               enQue(pointp);
           }

           if (isSafe(point.i - 1, point.j) == true) // check UP
           {
               visited[point.i - 1][point.j] = true;
               pointp.i = point.i - 1;
               pointp.j = point.j;
               //q.push(pointp);
               enQue(pointp);
           }
       }
   }
   return count1;
}

void resetvisited()
{
   for (int i = 0; i <N; i++)
       for (int j = 0; j <N; j++)
           visited[i][j] = false;
}

void bfs(int r, int c)
{
   count1 = 0;
   resetvisited();
   init_Que();
   bfsutil(r, c);
}

int main(int argc, char** argv)
{
   int T, test_case;
   int temp1, temp2;
   freopen("input.txt", "r", stdin);
   cin >> T;
   for (test_case = 0; test_case < T; test_case++)
   {
       resetvisited();
       MAXANSWER = INT_MIN;
       cin >> N;
       for (int i = 0; i <N-1; i++)
       {
           for (int j = 0; j<N-1; j++)
           {
               cin >> temp1;
               if (temp1 == 1)
                   leftWall[i][j] = true;
               else
                   leftWall[i][j] = false;
           }
       }

       for (int i = 0; i < N - 1; i++)
       {
           for (int j = 0; j < N - 1; j++)
           {
               cin >> temp2;
               if (temp2 == 1)
                   bottomWall[i][j] = true;
               else
                   bottomWall[i][j] = false;

           }
       }
       bfs(N-1, 0);
       cout << MAXANSWER << endl;
   }

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.