Algorithm


Problem Name: beecrowd | 2520

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2520

The Last Analógimôn

 

By Ricardo Oliveira, UFPR BR 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 & Try With Live Editor

Input

x
+
cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

x
+
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 & Try With Live Editor

Input

x
+
cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

x
+
cmd
5

#3 Code Example with Javascript Programming

Code - Javascript Programming


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

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

		return createInterface({
			input: createReadStream(path, readStreamOptions),
			crlfDelay: Infinity,
			terminal: false
		})
	}

	/**
	 * @param {import("node:fs").PathLike} path
	 * @param {BufferEncoding} encoding
	 */
	static create(path, encoding) {
		const RLI = LineReader.createReadLineInterface(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"

	const lineReader = LineReader.create(PATH, ENCODING)

	while (lineReader.hasNextLine()) {
		const sizes = await lineReader.nextLine()
		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)
	}

	if (lineReader.hasNextLine())
		lineReader.close()

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

main()
Copy The Code & Try With Live Editor

Input

x
+
cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

x
+
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 & Try With Live Editor

Input

x
+
cmd
4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Output

x
+
cmd
5
Advertisements

Demonstration


Previous
#2510 Beecrowd Online Judge Solution 2510 Batmain Solution in C, C++, Java, Js and Python
Next
#2523 Beecrowd Online Judge Solution 2523 Will's Message Solution in C, C++, Java, Js and Python