You are not logged in. Please login at www.codechef.com to post your questions!

×

Doubt : Direction Vector

This is the Solution for KNICOV problem.
This the another Problem on same lines from geeksforgeeks.
There are two arrays used named 'dx' and 'dy' which are common in both problems and named as 'Direction Vector' in gfgs solution.
I know they are used to somewhat check and validate next move in X and Y directions respectively.

But, I want to know how do you fill the values in these arrays?
And also can anyone share links to problems of these type?

asked 25 Aug '17, 11:41

sumedhk's gravatar image

4★sumedhk
2318
accept rate: 0%

edited 25 Aug '17, 11:44


A knight move is defined as follows: It moves to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. (from Wikipedia)

So if you are at the square $(x, y)$, you can either move to $(x+2, y+1)$, $(x+2, y-1)$, $(x-2, y+1)$, $(x-2, y-1)$, $(x+1, y+2)$, $(x+1, y-2)$, $(x-1, y+2)$, $(x-1, y-2)$. Therefore you can extract the arrays $dx = [2, 2, -2, -2, 1, 1, -1, -1]$ and $dy = [1, -1, 1, -1, 2, -2, 2, -2]$ and iterate over them with

for (int move = 0; move < 8; move++) {
    new_x = old_x + dx[move];
    new_x = old_y + dy[move];
}

The order of possible moves can obviously vary. So you would end up at different

Here are two game theory problems about knights: A Chessboard Game, Chessboard Game, Again!

link

answered 25 Aug '17, 12:12

afaxnraner's gravatar image

6★afaxnraner
5915
accept rate: 22%

got it, Thanks mate! @afaxnraner

(25 Aug '17, 12:25) sumedhk4★

direction array is used to go from a index to other indexes in certain directions as told in the question. The most common directions are going in 4 directions Up, Down, Left, Right, 8 directions Up, Down, Left, Right and 4 diagonal directions and knight directions(If you've played chess, you'd know how knight moves)

Now, we use 2 dimensional arrays to make a grid. suppose X,Y is the co-ordinate of the position in the grid. So how will you move upward direction. X+= (-1) and Y = 0. Add this in the direction array.

dx = {-1}
dy = {0}

Now, how will you move downward direction? X+= 1 and Y = 0. Add this also.

dx = {-1,1}
dy = {0,0}

Similarly after adding left and right directions, you will get,

dx = {-1,1,0,0}
dy = {0,0,-1,1}

So, now if you iterate through them and add them to X and Y one by one, you can move to all the 4 directions.

Here are the direction array of 8 direction movement and knight movement:

//8 direction movement
int dx[] = { -1, -1,  0, 1, 1, 1,  0, -1 };
int dy[] = {  0, -1, -1, -1,  0, 1, 1, 1 };


//knight movement
int dxK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int dyK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
link

answered 25 Aug '17, 12:13

sudip_95's gravatar image

4★sudip_95
7556
accept rate: 10%

1

@sudip_95 Thanks mate!

(25 Aug '17, 12:28) sumedhk4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,020
×302

question asked: 25 Aug '17, 11:41

question was seen: 150 times

last updated: 25 Aug '17, 12:29