Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live
Ocultar sin cambios
Sin ajuste de línea
Vista
Nivel de detalle
Resaltado de sintaxis

Untitled diff

Creado El diff nunca expira
77 eliminaciones
359 líneas
77 adiciones
354 líneas
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;
}
}

}
}
}
}
Diferencias guardadas