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 
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 |
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;
}
Input
Output
#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;
}
Input
Output
#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()
Input
Output
#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
Input
Output