CodeForces 370A Rook, Bishop and King(車，象，王到目的地的最小步數)

CodeForces 370A Rook, Bishop and King(車，象，王到目的地的最小步數)

Rook, Bishop and King Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Description

Little Petya is learning to play chess. He has already learned how to move a king, a rook and a bishop. Let us remind you the rules of moving chess pieces. A chessboard is 64 square fields organized into an 8?×?8 table. A field is represented by a pair of integers (r,?c) — the number of the row and the number of the column (in a classical game the columns are traditionally indexed by letters). Each chess piece takes up exactly one field. To make a move is to move a chess piece, the pieces move by the following rules:

A rook moves any number of fields horizontally or vertically.A bishop moves any number of fields diagonally.A king moves one field in any direction — horizontally, vertically or diagonally. The pieces move like that

Petya is thinking about the following problem: what minimum number of moves is needed fZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciBlYWNoIG9mIHRoZXNlIHBpZWNlcyB0byBtb3ZlIGZyb20gZmllbGQoPGVtPnI8L2VtPjxzdWIgY2xhc3M9"lower-index">1,?c₁) to field (r₂,?c₂)? At that, we assume that there are no more pieces besides this one on the board. Help him solve this problem.

Input

The input contains four integers r₁,?c₁,?r₂,?c₂ (1?≤?r₁,?c₁,?r₂,?c₂?≤?8) — the coordinates of the starting and the final field. The starting field doesn't coincide with the final one.

You can assume that the chessboard rows are numbered from top to bottom 1 through 8, and the columns are numbered from left to right 1 through 8.

Output

Print three space-separated integers: the minimum number of moves the rook, the bishop and the king (in this order) is needed to move from field (r₁,?c₁) to field (r₂,?c₂). If a piece cannot make such a move, print a 0 instead of the corresponding number.

Sample Input

Input

4 3 1 6

Output

2 1 3

Input

5 5 5 6

Output

1 0 1

題目大意：

車只能水平和豎直走，象走斜線，王走八個方向。

解題思路：

車和王不說，主要是象。如果起點和終點連線可以構成一個正方形的對角線，則象需要一步，即abs(x1-x2)==abs(y1-y2)；如果起點和終點可以通過兩步達到，則它媒介一個格子，再到終點，比如（3,1）到（4,6），可以經過（6,4），媒介的這個點會滿足一定的條件，即與起點可以構成正方形的對角線，與終點構成一個正方形的對角線，且這兩條對角線是互相垂直的，即斜率乘積為-1，即一個為1，一個為-1（因為棋盤的對角線斜率不是1就是-1）.

k1=1, y=x+b1, (y1=x1+b1,b1=y1-x1);

k2=-1, y=-x+b2, (y2=-x2+b2,b2=x2+y2);

交點坐標y為y=(b1+b2)/2 ;若存在這樣的格子，則y就為整數，表示能找到，此時步數為二，否則為0；

所以如果 (b1+b2)/%2!=0 --> (x2+y2+y1-x1)%2!=0,則 步數為0，其他情況為2.

[cpp] view plaincopy

1. #include
2. #include
3. #include
4. #include
5. using namespace std;
7. int main(){
8. int x1,x2,y1,y2;
9. while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF){
10. int a=1,b=2,c=max(abs(x1-x2),abs(y1-y2));//Max頭文件algorithm，abs頭文件cmath.
11. if(x1!=x2&&y1!=y2)a=2;
12. if(abs(x1-x2)==abs(y1-y2))
13. b=1;
14. else if((x2+y2+(y1-x1))%2!=0)
15. b=0;
16. printf("%d %d %d\n",a,b,c);
17. }
18. return 0;
19. }