Problem statement

A queen is standing on an \$n\$x\$n\$ chessboard. The chessboard's rows are numbered from \$1\$ to \$n\$, going from bottom to top; its columns are numbered from \$1\$ to \$n\$, going from left to right. Each square on the board is denoted by a tuple, \$(r,c)\$, describing the row, \$r\$, and column, \$c\$, where the square is located.

The queen is standing at position \$(r_q,c_q)\$ 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 \$(4,4)\$:

There are \$k\$ 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 \$(3,5)\$ in the diagram above would prevent the queen from attacking cells \$(3,5)\$, \$(2,6)\$, and \$(1,7)\$:

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 \$(r_q,c_q)\$.

Input Format

The first line contains two space-separated integers describing the respective values of \$n\$ (the side length of the board) and \$k\$ (the number of obstacles).

The next line contains two space-separated integers describing the respective values of \$r_q\$ and \$c_q\$, denoting the position of the queen.

Each line \$i\$ of the \$k\$ subsequent lines contains two space-separated integers describing the respective values \$r_i\$ of \$c_i\$ and , denoting the position of obstacle \$i\$.

Constraints

\$ 0 \leq n \leq 100000\$

\$ 0 \leq k \leq 100000\$

A single cell may contain more than one obstacle; however, it is guaranteed that there will never be an obstacle at position \$(r_q,c_q)\$ where the queen is located.

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 \$(4,4)\$ on a \$4\$x\$4\$ chessboard with no obstacles:

We then print the number of squares she can attack from that position, which is \$9\$.

My introduction of algorithm:

This algorithm is a medium one in hackerrank world codesprint 9 contest, and I like to code review the solution I wrote after the contest, instead of the one in the contest. Because in the contest, I did not encapsulate the 8 directions very well, I spent time to write code for each direction. And I am studying the open/ close principle, the idea of implementation is the similar, do not write if/ else code to discuss each direction. Enumerate all directions by iterating the directions array once:

// start from left, clockwise, left up, up, right up, right, ...
    public static int[] directions_row = new int[] {  0,  1, 1, 1, 0, -1, -1, -1 };
    public static int[] directions_col = new int[] { -1, -1, 0, 1, 1,  1,  0, -1 };

For example, left direction \$(0, -1)\$, clockwise, next direction is left-up, \$(1,-1)\$. Enumerate all directions, for each direction, starting from the position of queen, just increment one by one using two direction arrays if staying in the boundary of matrix and it is not an obstacle cell.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueenAttackII
{
  /*
   * January 30, 2017
   * problem statement:
   * https://www.hackerrank.com/contests/world-codesprint-9/challenges/queens-attack-2
   *            
   */
  public class Directions
  {
    // start from left, clockwise, left and up, up, right and up, right, 
    //            right and down, down, left and down
    public static int[] directions_row = new int[] {  0,  1, 1, 1, 0, -1, -1, -1 };
    public static int[] directions_col = new int[] { -1, -1, 0, 1, 1,  1,  0, -1 };

    public int rows { get; set; }      

    public Tuple<int, int> queen { set; get; }

    public Directions(int row, int col, int size)
    {
        queen = new Tuple<int, int>(row, col);
        
        rows = size;
    }

    public int CalculateTotal(Tuple<int, int>[] obstacles)
    {
        // put all obstacles in a hashset
        var obstacleHashed = new HashSet<Tuple<int, int>>();
        foreach (Tuple<int, int> obstacle in obstacles)
        {
            obstacleHashed.Add(obstacle);
        }

        // go over each direction
        int count = 0; 

        for (int i = 0; i < 8; i++)
        {
            int rowIncrement = directions_row[i];
            int colIncrement = directions_col[i]; 

            int runnerRow = queen.Item1 + rowIncrement; 
            int runnerCol = queen.Item2 + colIncrement; 
            
            while( runnerRow >= 0 && runnerRow < rows &&
                   runnerCol >= 0 && runnerCol < rows && 
                   !obstacleHashed.Contains(new Tuple<int,int>(runnerRow, runnerCol)))
            {
                runnerRow += rowIncrement;
                runnerCol += colIncrement; 

                count++; 
            }
        }

        return count; 
    }      
  }

  class Program
  {
    static void Main(string[] args)
    {
        ProcessInput();
    }

    public static void ProcessInput()
    {
        var data = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

        int rows = data[0];
        int countObstacles = data[1];

        var queen = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        var obstacles = new Tuple<int, int>[countObstacles];

        for (int i = 0; i < countObstacles; i++)
        {
            var obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            obstacles[i] = new Tuple<int, int>(obstacle[0] - 1, obstacle[1] - 1);
        }

        var directions = new Directions(queen[0] - 1, queen[1] - 1, rows);            
        Console.WriteLine(directions.CalculateTotal(obstacles));
    }
  }
}