Given a matrix mat[][] of n rows and m columns, consisting of 0’s and 1’s. The task is to complete the function findPerimeter which returns an integer denoting the perimeter of sub-figures consisting of only 1’s in the matrix.
For example
Perimeter of single 1 is 4 as it can be covered from all 4 side. Perimeter of double 11 is 6.
                            
|  1  |           |  1    1  |
                            
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space separated n and m denoting the size of the matrix mat[][] . Then in the next line are n*m space separated values of the matrix.
Output:
For each test case in a new line print the perimeter of sub-figure consisting only 1’s in the matrix.
Constraints:
1<=T<=100
1<=n, m<=20
Example(To be used for expected output):
Input:
2
1 2
1 1 
3 3
1 0 0 1 0 0 1 0 0
Output:
6
8
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: EASY
Tags: Geometry

Matrices

Data structures

Starter code: # Your task is to complete this function
# Function should return an integer
def findPerimeter(arr, n, m):
    # code here


Solutions:
from itertools import product

def findPerimeter(arr, n, m):
	perimeter = 0
	for (i, j) in product(range(n), range(m)):
		if arr[i][j] == 0:
			continue
		perimeter += 4
		if i > 0 and arr[i - 1][j] == 1:
			perimeter -= 2
		if j > 0 and arr[i][j - 1] == 1:
			perimeter -= 2
	return perimeter


def numofneighbour(mat, i, j):
	R = len(mat)
	C = len(mat[0])
	count = 0
	if i > 0 and mat[i - 1][j]:
		count += 1
	if j > 0 and mat[i][j - 1]:
		count += 1
	if i < R - 1 and mat[i + 1][j]:
		count += 1
	if j < C - 1 and mat[i][j + 1]:
		count += 1
	return count

def find(mat):
	(R, C) = (len(mat), len(mat[0]))
	perimeter = 0
	for i in range(0, R):
		for j in range(0, C):
			if mat[i][j]:
				perimeter += 4 - numofneighbour(mat, i, j)
	return perimeter

def findPerimeter(arr, n, m):
	return find(arr)


def findPerimeter(arr, n, m):
	count = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j]:
				count += i == 0 or not arr[i - 1][j]
				count += i == n - 1 or not arr[i + 1][j]
				count += j == 0 or not arr[i][j - 1]
				count += j == m - 1 or not arr[i][j + 1]
	return count


def findPerimeter(arr, n, m):
	peri = []
	visit = set()

	def dfs(i, j):
		if i >= n or j >= m or i < 0 or (j < 0) or (arr[i][j] == 0):
			peri.append(1)
			return
		if (i, j) in visit:
			return
		visit.add((i, j))
		dfs(i, j + 1)
		dfs(i, j - 1)
		dfs(i + 1, j)
		dfs(i - 1, j)
	for r in range(n):
		for c in range(m):
			if arr[r][c] == 1:
				dfs(r, c)
	return len(peri)


def peri(arr, i, j, n, m):
	if i < 0 or j < 0 or i >= n or (j >= m):
		return (1, arr)
	if arr[i][j] == 0:
		return (1, arr)
	if arr[i][j] == -1:
		return (0, arr)
	arr[i][j] = -1
	count = 0
	(cnt, arr) = peri(arr, i, j - 1, n, m)
	count += cnt
	(cnt, arr) = peri(arr, i - 1, j, n, m)
	count += cnt
	(cnt, arr) = peri(arr, i, j + 1, n, m)
	count += cnt
	(cnt, arr) = peri(arr, i + 1, j, n, m)
	count += cnt
	return (count, arr)

def findPerimeter(arr, n, m):
	count = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 1:
				(cnt, arr) = peri(arr, i, j, n, m)
				count += cnt
	return count


def findPerimeter(arr, n, m):
	count = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 1:
				if i - 1 < 0:
					count += 1
				elif arr[i - 1][j] == 0:
					count += 1
				if j - 1 < 0:
					count += 1
				elif arr[i][j - 1] == 0:
					count += 1
				if i + 1 >= n:
					count += 1
				elif arr[i + 1][j] == 0:
					count += 1
				if j + 1 >= m:
					count += 1
				elif arr[i][j + 1] == 0:
					count += 1
	return count


def check_surrounding1(row, col, n, m, a):
	dx = [0, 0, 1, -1]
	dy = [1, -1, 0, 0]
	surround = 0
	for i in range(4):
		if 0 <= row + dx[i] < n and 0 <= col + dy[i] < m and (a[row + dx[i]][col + dy[i]] == 1):
			surround += 1
	return 4 - surround

def findPerimeter(arr, n, m):
	perimeter = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 1:
				perimeter += check_surrounding1(i, j, n, m, arr)
	return perimeter


def findPerimeter(arr, n, m):
	perimeter = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 1:
				if i == 0:
					perimeter += 1
				if i == n - 1:
					perimeter += 1
				if i > 0 and arr[i - 1][j] == 0:
					perimeter += 1
				if i < n - 1 and arr[i + 1][j] == 0:
					perimeter += 1
				if j == 0:
					perimeter += 1
				if j == m - 1:
					perimeter += 1
				if j > 0 and arr[i][j - 1] == 0:
					perimeter += 1
				if j < m - 1 and arr[i][j + 1] == 0:
					perimeter += 1
	return perimeter


def findPerimeter(matrix, n, m):
	perimeter = 0
	for i in range(0, n):
		for j in range(0, m):
			if matrix[i][j] == 1:
				if i == 0:
					perimeter += 1
				elif matrix[i - 1][j] != 1:
					perimeter += 1
				if j == m - 1:
					perimeter += 1
				elif matrix[i][j + 1] != 1:
					perimeter += 1
				if j == 0:
					perimeter += 1
				elif matrix[i][j - 1] != 1:
					perimeter += 1
				if i == n - 1:
					perimeter += 1
				elif matrix[i + 1][j] != 1:
					perimeter += 1
	return perimeter


def findPerimeter(a, n, m):
	c = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == 1:
				top = 0
				left = 0
				right = 0
				bottom = 0
				summ = 0
				if i - 1 >= 0 and a[i - 1][j] == 1:
					top += 1
				if j - 1 >= 0 and a[i][j - 1] == 1:
					left += 1
				if i + 1 < n and a[i + 1][j] == 1:
					bottom += 1
				if j + 1 < m and a[i][j + 1] == 1:
					left += 1
				summ = top + right + bottom + left
				c += 4 - summ
	return c


def findPerimeter(arr, n, m):
	perimeter = 0
	for i in range(0, n):
		for j in range(0, m):
			if arr[i][j]:
				perimeter += 4 - numofneighbour(arr, i, j, n, m)
	return perimeter

def numofneighbour(mat, i, j, n, m):
	count = 0
	if i > 0 and mat[i - 1][j]:
		count += 1
	if j > 0 and mat[i][j - 1]:
		count += 1
	if i < n - 1 and mat[i + 1][j]:
		count += 1
	if j < m - 1 and mat[i][j + 1]:
		count += 1
	return count


def findPerimeter(grid, n, m):
	if not grid:
		return 0

	def sum_adjacent(i, j):
		adjacent = ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1))
		res = 0
		for (x, y) in adjacent:
			if x < 0 or y < 0 or x == len(grid) or (y == len(grid[0])) or (grid[x][y] == 0):
				res += 1
		return res
	count = 0
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 1:
				count += sum_adjacent(i, j)
	return count


def neighbours(mat, i, j, n, m):
	cnt = 0
	if i > 0 and mat[i - 1][j]:
		cnt += 1
	if i < n - 1 and mat[i + 1][j]:
		cnt += 1
	if j > 0 and mat[i][j - 1]:
		cnt += 1
	if j < m - 1 and mat[i][j + 1]:
		cnt += 1
	return cnt

def findPerimeter(arr, n, m):
	perimeter = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j]:
				perimeter += 4 - neighbours(arr, i, j, n, m)
	return perimeter


def findPerimeter(arr, n, m):
	peri = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j]:
				peri += 4 - numofneb(arr, i, j)
	return peri

def numofneb(m, i, j):
	count = 0
	if i > 0 and m[i - 1][j]:
		count += 1
	if j > 0 and m[i][j - 1]:
		count += 1
	if i < len(m) - 1 and m[i + 1][j]:
		count += 1
	if j < len(m[0]) - 1 and m[i][j + 1]:
		count += 1
	return count


def findPerimeter(arr, n, m):
	x = 0
	for i in range(n):
		flag = 0
		for j in range(m):
			if flag == 0 and arr[i][j] == 1:
				flag = 1
				x = x + 1
			if flag == 1 and arr[i][j] == 0:
				flag = 0
	for j in range(m):
		flag = 0
		for i in range(n):
			if flag == 0 and arr[i][j] == 1:
				flag = 1
				x = x + 1
			if flag == 1 and arr[i][j] == 0:
				flag = 0
	return x * 2


def findPerimeter(arr, n, m):
	per = 0

	def dfs(i, j):
		cnt = 0
		if i > 0 and arr[i - 1][j]:
			cnt += 1
		if j > 0 and arr[i][j - 1]:
			cnt += 1
		if i < n - 1 and arr[i + 1][j]:
			cnt += 1
		if j < m - 1 and arr[i][j + 1]:
			cnt += 1
		return cnt
	for i in range(n):
		for j in range(m):
			if arr[i][j]:
				per += 4 - dfs(i, j)
	return per


def numofneighbour(mat, i, j, R, C):
	count = 0
	if i > 0 and mat[i - 1][j]:
		count += 1
	if j > 0 and mat[i][j - 1]:
		count += 1
	if i < R - 1 and mat[i + 1][j]:
		count += 1
	if j < C - 1 and mat[i][j + 1]:
		count += 1
	return count

def findPerimeter(mat, R, C):
	perimeter = 0
	for i in range(0, R):
		for j in range(0, C):
			if mat[i][j]:
				perimeter += 4 - numofneighbour(mat, i, j, R, C)
	return perimeter