Journey of a Knight
InterviewTime limit1sMemory limit128 MB
Given an n by m board, find the minimum number of knight moves from cell (1,1) to cell (i,j), or report that it is unreachable.
- Level
Medium5 of 10
- Topics
- BFS, Graph, Shortest path, Implementation
- Solved
- No attempts yet
Problem
A rectangular chessboard has rows and columns, for a total of cells. Each cell is identified by a pair of coordinates , where is the row number () and is the column number (). A knight starts on the bottom-left cell .
The knight moves according to the standard chess rules: in a single move it jumps one cell in one direction and two cells in the perpendicular direction (or two cells and then one cell). In other words, from cell the knight can move to any of the following eight cells that lie on the board: and .
For example, if and and the knight is on cell , then in one move it can go to , , or .
You are given natural numbers , , , (, , , ). Determine the least possible number of moves the knight needs to reach cell , starting from cell .

Pic. 1

Pic. 2
Input
A single line containing four integers , , , and , separated by spaces.
Output
Output the minimum number of moves required for the knight to reach cell from cell . If cell cannot be reached, output the single word NEVAR instead.