## Algorithm

Problem Name: beecrowd | 2520

# The Last Analógimôn

By Ricardo Oliveira, UFPR Brazil

Timelimit: 1

Analógimôn Go! is a very popular game. During his quest, the player travels across many cities capturing virtual little monsters called analógimôns. You just entered a city that contains the very last analógimôn you still don’t have!

The city can be described as a grid with N rows and M columns. You are at a given position in the city, while the last analógimôn is at another position in the same city. In one second, you can move (exactly) one position to the north, to the south, to the west or to the east. Considering that the analógimôn does not move at all, you task is to determine the minimum amount of time you need to reach it.

The following figure shows the first sample input, and shows a path that can be made in 5 seconds. There are other paths that can be used that take the same amount of time, but there is no path that takes less time than this one.

## Input

The input contains several test cases. The first line of each test case contains two integers N and M (2 ≤ N, M ≤ 100), the number of rows and columns, respectively. Next N lines contains M integers each, describing the city. Integer 0 indicates an empty position; integer 1 indicates your position; and integer 2 indicates the analógimôn’s position. It is guaranteed that there is exactly one integer 1 and exactly one integer 2 in the test case, and that all other integers are equal to 0.

The input ends with end-of-file (EOF).

## Output

For each test case, print a line containing the minimum time needed to reach the last analógimôn, in seconds.

 Input Sample Output Sample 4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 5

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int i, j, a, b, x, y, p, q, z=0;

while (scanf("%d %d", &a, &b) != EOF)
{
int arr[a][b];

for (i = 0; i  <  a; ++i)
{
for (j = 0; j  <  b; ++j)
{
scanf("%d", &arr[i][j]);

if (arr[i][j] == 1)
{
x = i;
y = j;
}

if (arr[i][j] == 2)
{
p = i;
q = j;
}
}
}

z = abs(x-p)+abs(y-q);

printf("%d\n", z);
}

return 0;
}
``````
Copy The Code &

Input

cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

cmd
5

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cstdio>
#include <cstdlib>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
for (int i = 0; i  <  a; i++) {
for (int j = 0; j  <  b; j++) {
int davez;
scanf("%d", &davez);
if (davez == 1) x1 = i, y1 = j;
if (davez == 2) x2 = i, y2 = j;
}
}
printf("%d\n", abs(y1 - y2) + abs(x1 - x2));
}
return 0;
}
``````
Copy The Code &

Input

cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

cmd
5

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const { createReadStream } = require("node:fs")
const { createInterface } = require("node:readline")

/**
* @param {import("node:fs").PathLike} path
* @param {BufferEncoding} encoding
*/
static createReadLineInterface(path, encoding = "utf8") {
encoding: encoding,
flags: "r",
emitClose: true,
autoClose: true
}

return createInterface({
crlfDelay: Infinity,
terminal: false
})
}

/**
* @param {import("node:fs").PathLike} path
* @param {BufferEncoding} encoding
*/
static create(path, encoding) {

let EOF = false

const nextLineGenerator = (async function* () {
for await (const line of RLI)
yield line
})()

RLI.once("close", () => { EOF = true })

return {
hasNextLine: () => !EOF,
nextLine: async (/** @type {unknown} */ fn) => {
const { value } = (await nextLineGenerator.next())
return (typeof fn === "function") ? fn(value) : value
},
close: () => RLI.close()
}

}
}

async function main() {
const output = []

const PATH = "/dev/stdin"
const ENCODING = "utf8"

if (Boolean(sizes) === false) break // EOFile Condition

const [N, M] = sizes
.split(" ", 2)
.map(value => Number.parseInt(value, 10))

const positions = {
analogimons: { row: 0, col: 0 },
hunter: { row: 0, col: 0 }
}

for (let i = 0; i  <  N; i += 1) {
const line = (await lineReader.nextLine()).split(" ", M)

for (let j = 0; j  <  M; j += 1) {
if (line[j] === "1") { // Hunter
positions.hunter.row = i
positions.hunter.col = j
}
else if (line[j] === "2") { // Analogimon
positions.analogimons.row = i
positions.analogimons.col = j
}
}
}

const dist =
Math.abs(positions.analogimons.col - positions.hunter.col) +
Math.abs(positions.analogimons.row - positions.hunter.row)

output.push(dist)
}

console.log(output.join("\n"))
}

main()
``````
Copy The Code &

Input

cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

cmd
5

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
while True:
try:
n, m = [int(x) for x in input().split()]
matriz = []
for i in range(n):
matriz.append(input().split())

a = [(index, j.index('2')) for index, j in enumerate(matriz) if '2' in j]
b = [(index, j.index('1')) for index, j in enumerate(matriz) if '1' in j]

x = (abs(a[0][0] - b[0][0]))
y = (abs(a[0][1] - b[0][1]))
print(x + y)

except EOFError:
break
``````
Copy The Code &

Input

cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

cmd
5