A queen is standing on an chessboard. The chessboard's rows are numbered from to , going from bottom to top; its columns are numbered from to , going from left to right. Each square on the board is denoted by a tuple, , describing the row, , and column, , where the square is located.
The queen is standing at position and, in a single move, she can attack any square in any of the eight directions (left, right, up, down, or the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from :
There are obstacles on the chessboard preventing the queen from attacking any square that has an obstacle blocking the the queen's path to it. For example, an obstacle at location in the diagram above would prevent the queen from attacking cells , , and :
Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at .
Input Format
The first line contains two space-separated integers describing the respective values of (the side length of the board) and (the number of obstacles).
The next line contains two space-separated integers describing the respective values of and , denoting the position of the queen.
Each line of the subsequent lines contains two space-separated integers describing the respective values of and , denoting the position of obstacle .
The next line contains two space-separated integers describing the respective values of and , denoting the position of the queen.
Each line of the subsequent lines contains two space-separated integers describing the respective values of and , denoting the position of obstacle .
Constraints
- A single cell may contain more than one obstacle; however, it is guaranteed that there will never be an obstacle at position where the queen is located.
Subtasks
For of the maximum score:
For of the maximum score:
Output Format
Print the number of squares that the queen can attack from position .
Sample Input 0
4 0
4 4
Sample Output 0
9
Explanation 0
The queen is standing at position on a chessboard with no obstacles:
We then print the number of squares she can attack from that position, which is .
Sample Input 1
5 3
4 3
5 5
4 2
2 3
Sample Output 1
10
Explanation 1
The queen is standing at position on a chessboard with obstacles:
We then print the number of squares she can attack from that position, which is .
Code :-
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[][] chessBoard = new int[n][n];
int rQueen = in.nextInt()-1;
int cQueen = in.nextInt()-1;
int sum = 0;
chessBoard[rQueen][cQueen] = 1;
for(int a0 = 0; a0 < k; a0++){
int rObstacle = in.nextInt()-1;
int cObstacle = in.nextInt()-1;
// your code goes here
chessBoard[rObstacle][cObstacle]=-1;
}
//check all 8 ways
// and down
for(int i =rQueen+1;i<n;i++){
if(chessBoard[i][cQueen] ==0){
sum+=1;
}else{
break;
}
}
for(int i =rQueen-1;i>=0;i--){
if(chessBoard[i][cQueen] ==0){
sum+=1;
}else{
break;
}
}
//left and right
for(int i =cQueen+1;i<n;i++){
if(chessBoard[rQueen][i] ==0){
sum+=1;
}else{
break;
}
}
for(int i =cQueen-1;i>=0;i--){
if(chessBoard[rQueen][i] ==0){
sum+=1;
}else{
break;
}
}
//diagonal right
for(int row =rQueen-1,col=cQueen+1;row>=0 && col<n;row--,col++){
if(chessBoard[row][col] ==0){
sum+=1;
}else{
break;
}
}
for(int row =rQueen+1,col=cQueen-1;row<n && col>=0;row++,col--){
if(chessBoard[row][col] ==0){
sum+=1;
}else{
break;
}
}
//diagonal left
for(int row =rQueen-1,col=cQueen-1;row>=0 && col>=0;row--,col--){
if(chessBoard[row][col] ==0){
sum+=1;
}else{
break;
}
}
for(int row =rQueen+1,col=cQueen+1;row<n && col<n;row++,col++){
if(chessBoard[row][col] ==0){
sum+=1;
}else{
break;
}
}
System.out.println(sum);
}
}
No comments:
Post a Comment