Algorithm
Problem Name: beecrowd | 2163
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2163
The Force Awakens
By M.C. Pinto, UNILA 
Brazil
Timelimit: 1
A long time ago, in a galaxy far, far away...
After the decline of the Empire, scavengers are spread around the universe looking for a lost lightsaber. Everyone knows that a lightsaber emits an unique wave pattern: 42 surrounded by 7 all around. You have a wave sensor that scans a terrain with N x M cells. Look at the example below for an 4 x 7 terrain with a lightsaber in it (at position (2,4)).
You must write a program that, given an N x M terrain, looks for the lightsaber pattern in it. No scan have more than one lightsaber pattern.
Input
The first line of the input has two positive integers N and M, representing respectively the number of rows and the number of columns scanned in a terrain (3 ≤ N, M ≤ 1000). Each of the next N lines have M integers, describing the values scanned in each cell of the terrain (-100 ≤ Tij ≤ 100, for 1 ≤ i ≤ N and 1 ≤ j ≤ M).
Output
The output is a single line with 2 integers X and Y separated by one space. They represent the (X,Y)-coordinate of the lightsaber, if it is found. If the terrain doesn't have a lightsaber pattern, X and Y are both zero.
| Input Samples | Output Samples |
|
4 7 |
2 4 |
|
4 7 |
0 0 |
|
3 3 |
2 2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int main(void)
{
int a, b, i, j, x=-1, y=-1;
scanf("%i %i", &a, &b);
int arr[a][b];
for (i = 0; i < a; ++i)
{
for (j = 0; j < b; ++j)
scanf("%i", &arr[i][j]);
}
for (i = 0; i < a-1; ++i)
{
for (j = 0; j < b-1; ++j)
{
if (arr[i][j] == 42)
{
if (arr[i][j-1]==7 && arr[i][j+1]==7 && arr[i-1][j]==7 && arr[i+1][j]==7 && arr[i-1][j-1]==7 && arr[i-1][j+1]==7 && arr[i+1][j-1]==7 && arr[i+1][j+1]==7)
{
x=i;
y=j;
}
}
}
}
printf("%i %i\n", x+1, y+1);
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,M;
cin >> N >> M;
int a[N][M];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
cin >> a[i][j];
}
int x_axis=0,y_axis=0;
bool x=false;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(a[i][j] == 42)
{
if(i == 0||i == N-1||j == 0||j == M-1)
{
//x = true;
continue;
}
else
{
if(a[i-1][j-1]==7&&a[i-1][j]==7&&a[i-1][j+1]==7&&a[i][j-1]==7&&a[i][j+1]==7&&a[i+1][j-1]==7&&a[i+1][j]==7&&a[i+1][j+1]==7)
{
x_axis = i+1;
y_axis = j+1;
}
}
}
}
}
cout << x_axis << " "<< y_axis << endl;
return 0;
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
const values = input.split(/\s+/).map(value => parseInt(value));
const [N, M] = values.splice(0, 2);
const forceAwakens = (lines, columns) => {
const terrain = [];
for (let i = 0; i < lines; i++) {
terrain.push(values.splice(0, columns));
}
let line = 0;
let column = 0;
for (let i = 1; i < lines - 1; i++) {
for (let j = 1; j < columns - 1; j++) {
if (terrain[i][j] === 42) {
if (terrain[i - 1][j - 1] === 7 && terrain[i - 1][j] === 7 && terrain[i - 1][j + 1] === 7) {
if (terrain[i][j - 1] === 7 && terrain[i][j + 1] === 7) {
if (terrain[i + 1][j - 1] === 7 && terrain[i + 1][j] === 7 && terrain[i + 1][j + 1] === 7) {
line = i + 1;
column = j + 1;
return `${line} ${column}`;
}
}
}
}
}
}
return `${line} ${column}`;
};
console.log(forceAwakens(N, M));
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
n, m = [int(x) for x in input().split()]
t = []
possibleX = []
possibleY = []
for i in range(n):
t.append([int(x) for x in input().split()])
if (i > 0) and (i < n - 1) and (42 in t[i]):
indexes = [index for index, x in enumerate(t[i]) if x == 42]
possibleX.extend([i] * len(indexes))
possibleY.extend(indexes)
x = y = 0
for i in range(0, len(possibleX)):
if (possibleX[i] > 0) and (possibleX[i] < n-1) and (possibleY[i] > 0) and (possibleY[i] < m-1):
soma = 0
for i2 in range(possibleX[i]-1, possibleX[i] + 2):
for j2 in range(possibleY[i] - 1, possibleY[i] + 2):
soma += t[i2][j2]
if soma == 98:
x = possibleX[i] + 1
y = possibleY[i] + 1
break
print(x, y)
'''
if t[possibleX[i]-1][possibleY[i]-1] == t[possibleX[i]-1][possibleY[i]] == t[possibleX[i]-1][possibleY[i]+1] == 7:
if t[possibleX[i]][possibleY[i]-1] == t[possibleX[i]+1][possibleY[i]-1] == t[possibleX[i]+1][possibleY[i]] == 7:
if t[possibleX[i]+1][possibleY[i]+1] == t[possibleX[i]][possibleY[i]+1] == 7:
x = possibleX[i] + 1
y = possibleY[i] + 1
'''
Input
Output