Join Us
Loading Similar Posts
Entering edit mode
Question 1 : Space Planning For A House
The blueprint of a room a Is represented by a 2D array of 1's and 0s, such that 1 represents the walls, and 0 represents
the empty spaces .Please help group the empty spaces into rooms with labels matching their size i.e. if you group a bounded space into
a room, and the size of that enclosed space is 3 units. then replace the 0's in that space by 3 . For the case where the room is only 1 space, skip labelling it I.e. leave it as 0.
Input Format:
First line contains the number of rows r"
Second line contains the number of columns "c"
Each of the next r lines contain line of 0 and 1's of length "c"
Output Format:
Output contains "r" lines with each row containing the 1, 0 or label/room size measuring upto "c" cells in the row.
Assumptions:
- The outer boundary of the 2-D array is always 1, the rooms are always completely enclosed by walls,
- diagonal movement is not possible
- .Each position of the 2-D array counts as 1 unit of space
Constraints
Rows and columns will be 3<r , c<100
Sample Input
7
7
1 1 1 1 1 1 1
1 0 1 0 1 0 1
1 1 0 0 1 0 1
1 0 0 1 0 0 1
1 1 1 1 1 1 1
Sample Output
1 1 1 1 1 1 1
1 0 1 5 1 4 1
1 1 5 5 1 4 1
1 5 5 1 4 4 1
1 1 1 1 1 1 1
1 2 2 1 2 2 1
1 1 1 1 1 1 1
Question 2 - Plan Your Chess Moves
Mandy's elder brother Rob is supposed to be a chess whizkid. Mandy wants to test her brother's abilities and gives him a
challenge.
On a standard 8x8 chess board, she places one Knight at coordinates X. She then places Mother pawns at various
coordinates Yi [i=1 to M].
Rob's challenge is to determine the lowest number of moves the Knight needs to make to kill all the 'M' pawns. As we know,
a Knight move in L shape Le 2 horizontal & 1 vertical cells OR 2 vertical & 1 horizontal cells. Your goal is to help Rob beat
Mandy's challenge.
Assumptions:
Chess board is organized as 8x8 board with bottom left most cell having coordinates (0,0) and top right most is (7,7)
Constraints:
Maximum value of M is 8 as expected.
Input Format:
First line contains the number of pawns i.e "M" i.e. number of rows one for each coordinate
Second line contains the number entry in each coordinate le, constant 2
Next M lines contain the coordinates of the M pawns
Next line contains the number of Knights i.e. 1
Next line contains the number entry in each coordinate i.e. constant 2
Last line contains the coordinate of the Knight
Output Format:
Share the number of moves required to kill all the pawns. -1 if not possible to kill any of the pawns.
Sample Input 1:
2
2
1 2
2 4
1
2
0 0
Sample Output 1
2
Sample Explanation
There are 2 pawns I.e P1 at (1,2) and P2 at (2,4). The best strategy is for Knight at (0,0) to take the pawn P1 in first
move and then take P2 in the second move. So, total 2 moves.
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
#define int long long int
vector<int> dr = {2, -2, 1, -1, 2, -2, 1, -1};
vector<int> dc = {1, -1, -2, 2, -1, 1, 2, -2};
int dfs(vector<vector<int>>& vis, int r, int c, vector<vector<int>>& pwn, int cur, vector<vector<int>>& dp){
if(pwn[r][c]==1) cur--;
if(cur == 0) return 0;
if(dp[r][c]>-1) return dp[r][c];
vis[r][c] = 1;
int temp = INT_MAX;
for(int i = 0;i<8;i++){
int nr = r + dr[i];
int nc = c + dc[i];
if(nr < 8 && nr>=0 && nc<8 && nc>=0 && vis[nr][nc]==0){
temp = min(temp, 1+dfs(vis, nr, nc, pwn, cur, dp));
}
}
vis[r][c] = 0;
return dp[r][c] = temp;
}
signed main(){
vector<vector<int>> vis(8, vector<int>(8));
vector<vector<int>> pwn(8, vector<int>(8));
vector<vector<int>> dp(8, vector<int>(8, -1));
pwn[1][5] = 1;
pwn[2][4] = 1;
cout<<dfs(vis, 0, 0, pwn, 2, dp);
}
