Untitled diff
79 removals
359 lines
74 additions
354 lines
using System;
using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Linq;
using System.Linq;
using System.Text;
using System.Text;
using System.Threading.Tasks;
using System.Threading.Tasks;
namespace QueenAttack2
namespace QueenAttack2
{
{
class QueenAttack2
class QueenAttack2
{
{
internal class Directions
internal class Directions
{
{
public static int[] directions_row = new int[] { -1, -1, 0, 1, 1, 1, 0, -1 };
public static int[] directions_row = new int[] { -1, -1, 0, 1, 1, 1, 0, -1 };
public static int[] directions_col = new int[] { 0, -1, -1, -1, 0, 1, 1, 1 };
public static int[] directions_col = new int[] { 0, -1, -1, -1, 0, 1, 1, 1 };
public int rows;
public int rows;
public int[] minimumDistance;
public int[] minimumDistance;
public bool[] minimumDistanceExist;
public bool[] minimumDistanceExist;
public Tuple<int, int> queen {set; get;}
public Tuple<int, int> queen {set; get;}
public Directions(int row, int col, int size)
public Directions(int row, int col, int size)
{
{
queen = new Tuple<int, int>(row, col);
queen = new Tuple<int, int>(row, col);
minimumDistance = new int[8];
minimumDistance = new int[8];
minimumDistanceExist = new bool[8];
minimumDistanceExist = new bool[8];
rows = size;
rows = size;
}
}
/*
/*
* left, right, up, down, or the four diagonals
* left, right, up, down, or the four diagonals
* 8 directions - clockwise, starting from left.
* 8 directions - clockwise, starting from left.
*/
*/
public bool IsOneOfEightDirections(
public bool IsOneOfEightDirections(
int obstacle_row,
int obstacle_row,
int obstacle_col)
int obstacle_col)
{
{
return (obstacle_col == queen.Item2 ||
return (obstacle_col == queen.Item2 ||
obstacle_row == queen.Item1 ||
obstacle_row == queen.Item1 ||
Math.Abs(obstacle_row - queen.Item1) == Math.Abs(obstacle_col - queen.Item2)
Math.Abs(obstacle_row - queen.Item1) == Math.Abs(obstacle_col - queen.Item2)
);
);
}
}
/*
/*
* Go over 100000 obstacles, and find those 8 minimum one if there is.
* Go over 100000 obstacles, and find those 8 minimum one if there is.
*
*
*/
*/
public void Keep8MininumObstacles(Tuple<int,int>[] obstacles)
public void Keep8MininumObstacles(Tuple<int,int>[] obstacles)
{
{
for(int i = 0; i < obstacles.Length; i ++)
for(int i = 0; i < obstacles.Length; i ++)
{
{
Tuple<int, int> obstacle = obstacles[i];
Tuple<int, int> obstacle = obstacles[i];
if(!IsOneOfEightDirections(obstacle.Item1, obstacle.Item2))
if(!IsOneOfEightDirections(obstacle.Item1, obstacle.Item2))
{
{
continue;
continue;
}
}
UpdateOneOfDirection(obstacle);
UpdateOneOfDirection(obstacle);
}
}
}
}
/*
/*
*
*
*/
*/
private void UpdateOneOfDirection(Tuple<int, int> obstacle)
private void UpdateOneOfDirection(Tuple<int, int> obstacle)
{
{
bool isSameRow = obstacle.Item1 == queen.Item1;
bool isDirectionLeft = obstacle.Item1 == queen.Item1 && obstacle.Item2 < queen.Item2;
bool isSameCol = obstacle.Item2 == queen.Item2;
bool isDirectionRight = obstacle.Item1 == queen.Item1 && obstacle.Item2 > queen.Item2;
bool isObstacleLeft = obstacle.Item2 < queen.Item2;
bool isObstacleRight = obstacle.Item2 > queen.Item2;
bool isObstacleUp = obstacle.Item1 > queen.Item1;
bool isObstacleDown = obstacle.Item1 < queen.Item1;
bool isDirectionLeft = isSameRow && isObstacleLeft;
bool isDirectionRight = isSameRow && isObstacleRight;
bool isDirectionUp = isSameCol && isObstacleUp;
bool isDirectionUp = obstacle.Item1 > queen.Item1 && obstacle.Item2 == queen.Item2;
bool isDirectionDown = isSameCol && isObstacleDown;
bool isDirectionDown = obstacle.Item1 < queen.Item1 && obstacle.Item2 == queen.Item2;
bool isDirectionUpLeft = isObstacleUp && isObstacleLeft;
bool isDirectionUpLeft = obstacle.Item1 > queen.Item1 && obstacle.Item2 < queen.Item2;
bool isDirectionUpRight = isObstacleUp && isObstacleRight;
bool isDirectionUpRight = obstacle.Item1 > queen.Item1 && obstacle.Item2 > queen.Item2;
bool isDirectionDownRight = obstacle.Item1 < queen.Item1 && obstacle.Item2 > queen.Item2;
bool isDirectionDownLeft = obstacle.Item1 < queen.Item1 && obstacle.Item2 < queen.Item2;
bool isDirectionDownLeft = isObstacleDown && isObstacleLeft;
bool isDirectionDownRight = isObstacleDown && isObstacleRight;
// verify left, up, right, down
// direction left:
// direction left:
if (isDirectionLeft)
if (isDirectionLeft)
{
{
int current = Math.Abs(queen.Item2 - obstacle.Item2);
int current = Math.Abs(queen.Item2 - obstacle.Item2);
UpdateMinimumDistanceInfo(0, current);
UpdateMinimumDistanceInfo(0, current);
}
}
if (isDirectionUp)
if (isDirectionUpLeft)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(2, current);
UpdateMinimumDistanceInfo(1, current);
}
}
if (isDirectionRight)
if (isDirectionUp)
{
{
int current = Math.Abs(queen.Item2 - obstacle.Item2);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(4, current);
UpdateMinimumDistanceInfo(2, current);
}
}
if (isDirectionDown)
if (isDirectionUpRight)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(6, current);
UpdateMinimumDistanceInfo(3, current);
}
}
// verify 4 cross directions
if (isDirectionRight)
if (isDirectionUpLeft)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item2 - obstacle.Item2);
UpdateMinimumDistanceInfo(1, current);
UpdateMinimumDistanceInfo(4, current);
}
}
if (isDirectionUpRight)
if (isDirectionDownRight)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(3, current);
UpdateMinimumDistanceInfo(5, current);
}
}
if (isDirectionDownRight)
if (isDirectionDown)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(5, current);
UpdateMinimumDistanceInfo(6, current);
}
}
if (isDirectionDownLeft)
if (isDirectionDownLeft)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(7, current);
UpdateMinimumDistanceInfo(7, current);
}
}
}
}
/*
/*
* 8 directions, use directions_row, directions_col as instruction
* 8 directions, use directions_row, directions_col as instruction
*/
*/
private void UpdateMinimumDistanceInfo(int direction, int current)
private void UpdateMinimumDistanceInfo(int direction, int current)
{
{
if (!minimumDistanceExist[direction])
if (!minimumDistanceExist[direction])
{
minimumDistanceExist[direction] = true;
minimumDistance[direction] = current;
}
else
{
if (current < minimumDistance[direction])
{
{
minimumDistanceExist[direction] = true;
minimumDistance[direction] = current;
minimumDistance[direction] = current;
}
}
}
else
{
if (current < minimumDistance[direction])
{
minimumDistance[0] = current;
}
}
}
}
public int CalculateTotal()
public int CalculateTotal()
{
{
// public int[] minimumDistance;
// public bool[] minimumDistanceExist;
int total = 0;
int total = 0;
for(int i = 0; i < 8; i++)
for(int i = 0; i < 8; i++)
{
{
if(minimumDistanceExist[i])
if(minimumDistanceExist[i])
{
{
total += minimumDistance[i] - 1;
total += minimumDistance[i] - 1;
continue;
continue;
}
}
if(i == 0)
if(i == 0)
{
{
// direction left
// direction left
total += queen.Item2;
total += queen.Item2;
}
}
if (i == 2)
if(i == 1)
{
{
// direction up
// direction up-left
total += rows - queen.Item1 - 1;
total += CalculateUpLeftCount();
}
}
if (i == 4)
if(i == 2)
{
{
// direction right
// direction up
total += rows - queen.Item2 - 1;
total += rows - queen.Item1 - 1;
}
}
if (i == 6)
{
// direction down
total += queen.Item1;
}
if(i == 1)
{
// direction up-left
total += CalculateUpLeftCount();
}
if(i == 3)
if(i == 3)
{
{
// direction up-right
// direction up-right
total += CalculateUpRightCount();
total += CalculateUpRightCount();
}
}
if(i == 4)
{
// direction right
total += rows - queen.Item2 - 1;
}
if(i == 5 )
if(i == 5 )
{
{
// direction down-right
// direction down-right
total += CalculateDownRightCount();
total += CalculateDownRightCount();
}
}
if(i == 6)
{
// direction down
total += queen.Item1;
}
if(i == 7)
if(i == 7)
{
{
// direction down-left
// direction down-left
total += CalculateDownLeftCount();
total += CalculateDownLeftCount();
}
}
}
}
return total;
return total;
}
}
private int CalculateUpLeftCount()
private int CalculateUpLeftCount()
{
{
int row = queen.Item1;
int row = queen.Item1;
int col = queen.Item2;
int col = queen.Item2;
int count = 0;
int count = 0;
while(row < rows -1 && col > 0)
while(row < rows -1 && col > 0)
{
{
row++;
row++;
col--;
col--;
count++;
count++;
}
}
return count;
return count;
}
}
private int CalculateUpRightCount()
private int CalculateUpRightCount()
{
{
int row = queen.Item1;
int row = queen.Item1;
int col = queen.Item2;
int col = queen.Item2;
int count = 0;
int count = 0;
while(row < rows -1 && col < rows - 1)
while(row < rows -1 && col < rows - 1)
{
{
row++;
row++;
col++;
col++;
count++;
count++;
}
}
return count;
return count;
}
}
private int CalculateDownRightCount()
private int CalculateDownRightCount()
{
{
int row = queen.Item1;
int row = queen.Item1;
int col = queen.Item2;
int col = queen.Item2;
int count = 0;
int count = 0;
while(row > 0 && col < rows - 1)
while(row > 0 && col < rows - 1)
{
{
row--;
row--;
col++;
col++;
count++;
count++;
}
}
return count;
return count;
}
}
private int CalculateDownLeftCount()
private int CalculateDownLeftCount()
{
{
int row = queen.Item1;
int row = queen.Item1;
int col = queen.Item2;
int col = queen.Item2;
int count = 0;
int count = 0;
while(row > 0 && col > 0)
while(row > 0 && col > 0)
{
{
row--;
row--;
col--;
col--;
count++;
count++;
}
}
return count;
return count;
}
}
}
}
static void Main(string[] args)
static void Main(string[] args)
{
{
ProcessInput();
ProcessInput();
//RunSampleTestcase();
//RunSampleTestcase();
//RunSampleTestcase2();
//RunSampleTestcase2();
}
}
public static void RunSampleTestcase()
public static void RunSampleTestcase()
{
{
Directions directions = new Directions(3, 3, 4);
Directions directions = new Directions(3, 3, 4);
var obstacles = new Tuple<int, int>[0];
var obstacles = new Tuple<int, int>[0];
directions.Keep8MininumObstacles(obstacles);
directions.Keep8MininumObstacles(obstacles);
Console.WriteLine(directions.CalculateTotal());
Console.WriteLine(directions.CalculateTotal());
}
}
/*
/*
* 5 3
* 5 3
* 4 3
* 4 3
* 5 5
* 5 5
* 4 2
* 4 2
* 2 3
* 2 3
*
*
*/
*/
public static void RunSampleTestcase2()
public static void RunSampleTestcase2()
{
{
Directions directions = new Directions(3, 2, 5);
Directions directions = new Directions(3, 2, 5);
var obstacles = new Tuple<int, int>[]{
var obstacles = new Tuple<int, int>[]{
new Tuple<int,int>(4,4),
new Tuple<int,int>(4,4),
new Tuple<int,int>(3,1),
new Tuple<int,int>(3,1),
new Tuple<int,int>(1,2)
new Tuple<int,int>(1,2)
};
};
directions.Keep8MininumObstacles(obstacles);
directions.Keep8MininumObstacles(obstacles);
Console.WriteLine(directions.CalculateTotal());
Console.WriteLine(directions.CalculateTotal());
}
}
public static void ProcessInput()
public static void ProcessInput()
{
{
int[] data = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int[] data = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int rows = data[0];
int rows = data[0];
int countObstacles = data[1];
int countObstacles = data[1];
int[] queen = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int[] queen = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
var obstacles = new Tuple<int, int>[countObstacles];
var obstacles = new Tuple<int, int>[countObstacles];
for (int i = 0; i < countObstacles; i++)
for (int i = 0; i < countObstacles; i++)
{
{
int[] obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int[] obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
obstacles[i] = new Tuple<int, int>(obstacle[0]-1, obstacle[1]-1);
obstacles[i] = new Tuple<int, int>(obstacle[0]-1, obstacle[1]-1);
}
}
Directions directions = new Directions(queen[0] -1, queen[1] - 1, rows);
Directions directions = new Directions(queen[0] -1, queen[1] - 1, rows);
directions.Keep8MininumObstacles(obstacles);
directions.Keep8MininumObstacles(obstacles);
Console.WriteLine(directions.CalculateTotal());
Console.WriteLine(directions.CalculateTotal());
}
}
/*
/*
* Process all obstacles one by one, determined if the obstacle is on 8 direction.
* Process all obstacles one by one, determined if the obstacle is on 8 direction.
* If it is 8 directions, then update minimum distance one.
* If it is 8 directions, then update minimum distance one.
* The total obstacles are up to 100000, we only need to keep up to 8 obstacles
* The total obstacles are up to 100000, we only need to keep up to 8 obstacles
*/
*/
public static IList<Tuple<int, int>> ProcessObstaclesKeep8withMinimuDistance(int n, int x, int y, Tuple<int,int>[] obstacles)
public static IList<Tuple<int, int>> ProcessObstaclesKeep8withMinimuDistance(int n, int x, int y, Tuple<int,int>[] obstacles)
{
{
IList<Tuple<int, int>> minimumOne = new List<Tuple<int, int>>();
IList<Tuple<int, int>> minimumOne = new List<Tuple<int, int>>();
return minimumOne;
return minimumOne;
}
}
}
}
}
}