URI / BEE CROWD 1087 - Queen Solution in C , C++ , Python , JavaScript

URI / BEE CROWD 1087 - Queen Solution in C/ C++ / Python / JavaScript | URI Online Judge Solution 1087 - Queen

beecrowd | 1087

Queen

By Fábio Dias Moreira  Brazil

Timelimit: 1

The game of Chess has several pieces with curious movements. One of them is the Queen, which can move any number of squares in any direction: in the same line, in the same column or in any of the diagonals, as illustrated by the figure below (black dots represent positions the queen may reach in one move):



The great Chess Master Kary Gasparov invented a new type of chess problem: given the position of a queen in an empty standard chess board (that is, an 8 x 8 board) how many moves are needed so that she reaches another given square in the board?

Kary found the solution for some of those problems, but is having a difficult time to solve some others, and therefore he has asked that you write a program to solve this type of problem.

Input

The input contains several test cases. The only line of each test case contains four integers X1Y1X2 and Y2 (1 ≤ X1, Y1, X2, Y2 ≤ 8). The queen starts in the square with coordinates (X1, Y1), and must finish at the square with coordinates (X2, Y2). In the chessboard, columns are numbered from 1 to 8, from left ro right; lines are also numbered from 1 to 8, from top to bottom. The coordinates of a square in line X and column Y are (X, Y).

The end of input is indicated by a line containing four zeros, separated by spaces.

Output

For each test case in the input your program must print a single line, containing an integer, indicating the smallest number of moves needed for the queen to reach the new position.

Input SampleOutput Sample

4 4 6 2
3 5 3 5
5 5 4 3
0 0 0 0

1
0
2

                                                                                       Demonstration:


A queen in chess can move:
1. Horizontally
2. Vertically
3. Diagonally

Given two positions (x1, y1) and (x2, y2), the goal is to find the minimum number of moves required for the queen to move from the starting position to the target position.

1. Same Position:

                If (x1, y1) == (x2, y2), the queen is already at the target position. So, 0 moves are needed.

2. Single Move:


If the target square is in the same row, column, or diagonal as the start, the queen can reach it in 1 move.

To check if they’re on the same row or column:

                        Same row: 
                                                    𝑥1 == 𝑥2
                                                    x1 == x2
                        Same column: 
                                                    𝑦1 == 𝑦2
                                                    y1 == y2
To check if they’re on the same diagonal:
                                         𝑥1 − 𝑥2 ∣ ==∣ 𝑦1−𝑦2 
                                        ∣ x1 − x2 ∣ ==∣ y1 − y2 
 (absolute difference between rows equals absolute difference between columns)

3. Two Moves :


If none of the above conditions are met, the queen can reach any of the target in 2 moves by moving first to an intermediate square and then from there to the destination.

Note: Always remember to add  endl otherwise you will get Presentation error


N.B: Don't copy paste the code as same. Just try to understand it and try yourself.

 BEE CROWD / URI Problem 1087 Solution in C :   

  BEE CROWD / URI Online Judge 1087 Solve  in C :      

#include <stdio.h>
#include <stdlib.h>
int main() {
    int x1, y1, x2, y2;
    while (scanf("%d %d %d %d", &x1, &y1, &x2, &y2), x1 || y1 || x2 || y2) {
        if (x1 == x2 && y1 == y2)
            printf("0\n");
        else if (x1 == x2 || y1 == y2 || abs(x1 - x2) == abs(y1 - y2))
            printf("1\n");
        else
            printf("2\n");
    }
    return 0;
}

0 Response to URI / BEE CROWD 1087 - Queen Solution in C , C++ , Python , JavaScript

Post a Comment