## Algorithm

Problem Name: beecrowd | 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 ≤ iN and 1 ≤ jM).

## 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 11 12 7 7 7 13 14 15 6 7 42 7 7 42 98 -5 7 7 7 42 7 -1 42 3 9 7 7 7 2 4

 4 7 11 12 7 7 7 13 14 15 6 7 12 7 7 42 98 -5 7 7 7 42 7 -1 42 3 9 7 7 7 0 0

 3 3 7 7 7 7 42 7 7 7 7 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;
}
``````
Copy The Code &

Input

cmd
4 7 11 12 7 7 7 13 14 15 6 7 42 7 7 42 98 -5 7 7 7 42 7 -1 42 3 9 7 7 7

Output

cmd
2 4

### #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;
}
``````
Copy The Code &

Input

cmd
4 7 11 12 7 7 7 13 14 15 6 7 42 7 7 42 98 -5 7 7 7 42 7 -1 42 3 9 7 7 7

Output

cmd
2 4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
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));
``````
Copy The Code &

Input

cmd
4 7 11 12 7 7 7 13 14 15 6 7 12 7 7 42 98 -5 7 7 7 42 7 -1 42 3 9 7 7 7

Output

cmd
0 0

### #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
'''
``````
Copy The Code &

Input

cmd
4 7 11 12 7 7 7 13 14 15 6 7 12 7 7 42 98 -5 7 7 7 42 7 -1 42 3 9 7 7 7

Output

cmd
0 0