Confronta il testo

Trova la differenza tra due file di testo

Visualizzazione

Layout
Livello di dettaglio
Sintassi

Elaborazione

Untitled diff

Creato Il diff non scade mai
81 rimozioni
359 linee
80 aggiunte
354 linee
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 isDirectionUp = obstacle.Item1 > queen.Item1 && obstacle.Item2 == queen.Item2;
bool isDirectionRight = isSameRow && isObstacleRight;
bool isDirectionDown = obstacle.Item1 < queen.Item1 && obstacle.Item2 == queen.Item2;


bool isDirectionUp = isSameCol && isObstacleUp;
bool isDirectionUpLeft = obstacle.Item1 > queen.Item1 && obstacle.Item2 < queen.Item2;
bool isDirectionDown = isSameCol && isObstacleDown;
bool isDirectionUpRight = obstacle.Item1 > queen.Item1 && obstacle.Item2 > queen.Item2;

bool isDirectionUpLeft = isObstacleUp && isObstacleLeft;
bool isDirectionDownRight = obstacle.Item1 < queen.Item1 && obstacle.Item2 > queen.Item2;
bool isDirectionUpRight = isObstacleUp && isObstacleRight;
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 to lines 95-100
if (isDirectionUp)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(2, current);
}

Text moved to lines 107-112
if (isDirectionRight)
{
int current = Math.Abs(queen.Item2 - obstacle.Item2);
UpdateMinimumDistanceInfo(4, current);
}

Text moved to lines 119-124
if (isDirectionDown)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(6, current);
}

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


Text moved from lines 98-103
if (isDirectionUp)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
UpdateMinimumDistanceInfo(2, current);
}

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


Text moved from lines 104-109
if (isDirectionRight)
{
int current = Math.Abs(queen.Item2 - obstacle.Item2);
UpdateMinimumDistanceInfo(4, current);
}

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


Text moved from lines 110-115
if (isDirectionDown)
{
int current = Math.Abs(queen.Item1 - obstacle.Item1);
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;
minimumDistanceExist[direction] = true;
minimumDistance[direction] = current;
minimumDistance[direction] = current;
}
}
else
else
{
{
if (current < minimumDistance[direction])
if (current < minimumDistance[direction])
{
{
minimumDistance[direction] = current;
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 with changes to lines 177-182 (99.7% similarity)
if (i == 2)
{
// direction up
total += rows - queen.Item1 - 1;
}

Text moved with changes to lines 189-194 (99.6% similarity)
if (i == 4)
{
// direction right
total += rows - queen.Item2 - 1;
}

Text moved with changes to lines 201-206 (94.2% similarity)
if (i == 6)
{
// direction down
total += queen.Item1;
}

if(i == 1)
if(i == 1)
{
{
// direction up-left
// direction up-left
total += CalculateUpLeftCount();
total += CalculateUpLeftCount();
}
}


Text moved with changes from lines 178-183 (99.7% similarity)
if(i == 2)
{
// direction up
total += rows - queen.Item1 - 1;
}

if(i == 3)
if(i == 3)
{
{
// direction up-right
// direction up-right
total += CalculateUpRightCount();
total += CalculateUpRightCount();
}
}


Text moved with changes from lines 184-189 (99.6% similarity)
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();
}
}


Text moved with changes from lines 190-195 (94.2% similarity)
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