아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

NMABCD

시간 제한1초메모리 제한1024 MB

요약
각 격자와 두 칸이 주어질 때, 시작 칸에서 도착 칸까지 단순 경로로 방문할 수 있는 최대 칸 수를 구한다.
난이도

보통10점 중 6점

유형
그래프, 그리디, 구현, 수학
정답자
아직 제출이 없습니다

문제

정수 NN, MM, AA, BB, CC, DD가 주어진다. 다음을 구해보자.

  • 격자판의 크기는 N×MN \times M이다.
  • 행과 열의 번호는 11부터 시작한다.
  • 시작 위치는 AA행, BB열이다.
  • 도착 위치는 CC행, DD열이다.
  • 각 칸은 최대 한 번만 방문할 수 있다.
  • 한 칸에서 다른 칸으로의 이동은 위, 아래, 오른쪽, 왼쪽으로 인접한 칸으로만 가능하다.
  • 최대한 많은 칸을 방문해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 QQ가 주어진다. 둘째 줄부터 QQ개의 줄에 테스트 케이스의 정보가 주어진다. 테스트 케이스의 정보는 한 줄로 이루어져 있고, NN, MM, AA, BB, CC, DD가 공백으로 구분되어 있다.

출력

각각의 테스트 케이스마다 방문할 수 있는 최대 칸의 수를 출력한다.

제한

  • 1≤N,M≤5,0001 ≤ N , M ≤ 5\\,000
  • 1≤Q≤1,6001 ≤ Q ≤ 1\\,600
  • 2≤N⋅M≤100,0002 ≤ N \cdot M ≤ 100\\,000
  • 1≤A,C≤N1 ≤ A, C ≤ N
  • 1≤B,D≤M1 ≤ B, D ≤ M
  • (A,B)≠(C,D)(A, B) ≠ (C, D)

예제1

  1. 예제 1

    입력
    2
2 3 1 1 2 2
3 3 1 1 3 3
    예상 출력
    5
9