Confronta il testo

Trova la differenza tra due file di testo

Real-time diff
Unified diff
Collapse lines
Highlight change
Syntax highlighting
Strumenti
Diffchecker Desktop icon
Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker DesktopLearn more

Untitled diff

Created Diff never expires
66 removals
359 lines
68 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);
}
}


Text moved from lines 117-122
if (isDirectionUpLeft)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(1, current);
}

if (isDirectionUp)
if (isDirectionUp)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(2, current);
UpdateMinimumDistanceInfo(2, current);
}
}


Text moved from lines 123-128
if (isDirectionUpRight)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(3, current);
}

if (isDirectionRight)
if (isDirectionRight)
{
{
int current = Math.Abs(queen.Item2 - obstacle.Item2);
int current = Math.Abs(queen.Item2 - obstacle.Item2);
UpdateMinimumDistanceInfo(4, current);
UpdateMinimumDistanceInfo(4, current);
}
}


Text moved from lines 129-132
if (isDirectionDownRight)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(5, current);
}

if (isDirectionDown)
if (isDirectionDown)
{
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(6, current);
UpdateMinimumDistanceInfo(6, current);
}
}


// verify 4 cross directions
Text moved to lines 89-94
if (isDirectionUpLeft)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(1, current);
}

Text moved to lines 101-106
if (isDirectionUpRight)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(3, current);
}

Text moved to lines 113-116
if (isDirectionDownRight)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(5, 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;
}
}


Text moved from lines 196-199
if (i == 2)
if(i == 1)
{
// direction up-left
total += CalculateUpLeftCount();
}

if(i == 2)
{
{
// direction up
// direction up
total += rows - queen.Item1 - 1;
total += rows - queen.Item1 - 1;
}
}


if (i == 4)
{
// direction right
total += rows - queen.Item2 - 1;
}

if (i == 6)
{
// direction down
total += queen.Item1;
}

Text moved to lines 171-174
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;
}
}

}
}
}
}
Diff salvati