Amazon Interview Question Software Engineer / Developers
Country: United States
import java.util.Stack;
class Cell{
int x;
int y;
int value;
boolean visited;
Cell(int x, int y, boolean visited, int value){
this.x=x;
this.y=y;
this.visited=visited;
this.value=value;
}
}
public class Shapes {
/**
* @param args
*/
static Cell cell[][]=null;
static void processCell(int icounter,int jcounter){
Stack<Cell> stack=new Stack<Cell>();
stack.push(cell[icounter][jcounter]);
while(!stack.isEmpty()){
Cell getcell=stack.pop();
getcell.visited=true;
System.out.println("Visited "+getcell.x+":"+getcell.y);
if((getcell.x+1)<=(cell.length-1)){
if(cell[getcell.x+1][getcell.y].value==1){
stack.push(cell[getcell.x+1][getcell.y]);
}
}
if((getcell.y+1)<=(cell.length-1)){
if(cell[getcell.x][getcell.y+1].value==1){
stack.push(cell[getcell.x][getcell.y+1]);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[][] = { {1, 0, 1, 0, 1},
{1, 1, 0, 1, 0},
{1, 1, 0, 1, 0},
{1, 0, 1, 0, 0}};
cell=new Cell[array.length][array[0].length];
for(int icounter=0;icounter<array.length;icounter++){
for(int jcounter=0;jcounter<array[0].length;jcounter++){
cell[icounter][jcounter]=new Cell(icounter,jcounter,false, array[icounter][jcounter]);
}
}
int shapeCounter = 0;
for(int icounter=0;icounter<array.length;icounter++){
for(int jcounter=0;jcounter<array[0].length;jcounter++){
System.out.println(icounter+" # "+jcounter);
if(!cell[icounter][jcounter].visited){
System.out.println(icounter+","+jcounter);
if(cell[icounter][jcounter].value==1){
processCell(icounter,jcounter);
shapeCounter++;
}
}
}
}
System.out.println("Shape Counter: "+shapeCounter);
}
}
int temp = 0;
int counter = 0;
for (int i = 1; i < n-1; i++)
{
for (int j = 1; j < m-1; j++)
{
temp = A[i, j];
if (A[i, j] == 0)
A[i, j] = 0;
else
{
A[i, j] += (A[i, j - 1] - A[i - 1, j - 1]);
A[i, j] += (A[i - 1, j] - A[i - 1, j - 1]);
if ((A[i, j] > 1 && A[i, j + 1] == 0) || (A[i, j] > 1 && A[i + 1, j] == 0))
counter++;
}
}
}
I agree with the use of Flood fill algorithm but How can you use BFS to achieve the desired result.. DFS might be an option. Please let me know if i am wrong.
public class CountShapes{
public static void main(String []args){
int num[][]={{1,1,0,0,1},
{1,0,0,1,0},
{1,1,0,1,0},
{0,0,1,0,0}};
int counter=0,rCount=0,cCount=0;
//Counting Coulmn Shapes
for(int i=0;i<5;i++){
counter=0;
for(int j=0;j<4;j++){
if(num[j][i]==1)
counter=counter+1;
else{
if(counter>=2)
cCount=cCount+1;
counter=0;
}
}
if(counter>=2)
cCount=cCount+1;
}
//Counting Row Shapes
for(int i=0;i<4;i++){
counter=0;
for(int j=0;j<5;j++){
if(num[i][j]==1)
counter=counter+1;
else{
if(counter>=2)
rCount=rCount+1;
counter=0;
}
}
if(counter>=2)
rCount=rCount+1;
}
System.out.println("Total Shapes:"+(rCount+cCount));
}
}
You can use anything similar to graph search to get the disjoint sets of connected 1's.
@Srikanth
what result will be returned for the matrix?
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1
expected: 1 because the entire matrix is the single shape
public class CountShapes{
public static void main(String []args){
int num[][]={{1,1,0,0,1},
{1,0,0,1,0},
{1,1,0,1,0},
{0,0,1,0,0}};
int counter=0,rCount=0,cCount=0;
//Counting Coulmn Shapes
for(int i=0;i<5;i++){
counter=0;
for(int j=0;j<4;j++){
if(num[j][i]==1)
counter=counter+1;
else{
if(counter>=2)
cCount=cCount+1;
counter=0;
}
}
if(counter>=2)
cCount=cCount+1;
}
//Counting Row Shapes
for(int i=0;i<4;i++){
counter=0;
for(int j=0;j<5;j++){
if(num[i][j]==1)
counter=counter+1;
else{
if(counter>=2)
rCount=rCount+1;
counter=0;
}
}
if(counter>=2)
rCount=rCount+1;
}
System.out.println("Total Shapes:"+(rCount+cCount));
}
}
class Cell {
int x;
int y;
Cell(int x, int y){
this.x = x;
this.y = y;
}
}
List<Cell> generateChildCells(int x, int y, int numRows, int numCols, boolean[][] hitMap) {
ArrayList<Cell> cCells = new ArrayList();
// Search for four directions
if (x+1 < numRows && !hitMap[x+1][y]) cCells.add(new Cell(x+1, y));
if (y+1 < numCols && !hitMap[x][y+1]) cCells.add(new Cell(x, y+1));
if (x > 1 && !hitMap[x-1][y]) cCells.add(new Cell(x-1, y));
if (y > 1 && !hitMap[x][y-1]) cCells.add(new Cell(x, y-1));
return cCells;
}
public static void countNumShapes(int[][] mat, int numRows, int numCols) {
// This is not a really class, any queue should be fine
Queue q = new Queue();
// initialize a hit map
boolean[][] hitMap = new boolean[numRows][numCols];
for(int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
hitMap[i][j] = false;
}
}
// Perform the search and count
int count = 0;
for(int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
if(hitMap[i][j] = true) continue;
if(mat[i][i] == 0) continue;
// if we see a 1 in the matrix, start a search
q.enqueue(new Cell(i, j))
count ++
while(!q.isEmpty()) {
Cell c = q.dequeue();
hitMap[c.x][c.y] = true;
for(Cell ch: generateChildCells(c)){
q.enqueue(ch)
}
}
}
return count;
}
We use a queue here to perform the search, the algorithm thus is a BFS. If we use a Stack instead, the algorithm will turn out to be a DFS.
Sorry, in the generateChildCells method, each condition should also check if the cell is equal to 1, add the cell only if it is a one cell.
Nice problem!
Use "quick union" method to find if a cell is part of a cluster. For details look up "Algorithms" by Sedgewick and the percolation problem. Essentially, when a cell is connected to another cell, it forms a tree (not a binary tree). When a third cell is connected, it gets added to the tree. A tree can get connected to another tree to form one big tree. To find if two cells are connected see if they have a common root.
Once you have implemented quick union, start with an array of size NxN with all entries 0 (empty). Then start scanning the matrix. For every cell which is 1, see if any of its neighbors are also 1. If 1, create a union with that neighbor. If not, create a new tree. At the end, count the number of individual trees - that's your answer.
If M=NxN, where N is the width of the matrix, max height of tree is log(M), so each lookup is at most O(log M). Do this at most M time, so worst case is O(M log(M))
This seems overly complicated, when this problem is easily solved in O(M) by traversing adjacent cells and leaving breadcrumbs. See the Python solution, for example.
An array can be represented as a tree.
No matter what algorithm you use, the fact that you would have to look at each cell to figure out if it is a 1 or 0, sets the lower bound for the achievable time complexity to O(rows * cols). It cannot be better than this!
I am using this comment to post the quick-union-based solution that requires O(M) space and has O(M log M) complexity where M = rows * cols.. hope it will be useful..
class Shapes
{
private readonly int[] _aux;
private readonly int[] _sizes;
private readonly int _rows;
private readonly int[,] _input;
private readonly int _cols;
private readonly Dictionary<int, bool> _components = new Dictionary<int, bool>();
private int GetAuxIndex(int ri, int ci)
{
return ri*_cols + ci;
}
private int Find(int index)
{
while (_aux[index] != index)
index = _aux[index];
return index;
}
private void Union(int s1, int s2)
{
var c1 = Find(s1);
var c2 = Find(s2);
if (c1 == c2)
return;
if (_sizes[c1] < _sizes[c2])
{
_aux[c1] = _aux[c2];
_sizes[c2] += _sizes[c1];
_components[c2] = true;
}
else
{
_aux[c2] = _aux[c1];
_sizes[c1] += _sizes[c2];
_components[c1] = true;
}
}
private void TryUnion(int index, int ri, int ci)
{
if (_input[ri, ci] == 0)
return;
var index2 = GetAuxIndex(ri, ci);
Union(index, index2);
}
public Shapes(int[,] input)
{
_rows = input.GetLength(0);
_cols = input.GetLength(1);
var n = _rows*_cols;
_input = input;
_aux = new int[n];
_sizes = new int[n];
for (int i = 0; i < _aux.Length; i++)
{
_aux[i] = i;
_sizes[i] = 1;
}
for (var ri = 0; ri < _rows; ri++)
{
for (var ci = 0; ci < _cols; ci++)
{
var next = input[ri, ci];
var nextIndex = GetAuxIndex(ri, ci);
if (next == 0)
continue;
if (ci > 0)
{
TryUnion(nextIndex, ri, ci-1);
}
if (ri > 0)
{
TryUnion(nextIndex, ri-1, ci);
}
}
}
var shapes = 0;
for (var i = 0; i < _aux.Length; i++)
{
var ind = Find(i);
var size = _sizes[ind];
if (size==1 && _input[i/_cols, i%_cols] == 1)
shapes++;
}
shapes += _components.Count;
Console.WriteLine(shapes);
}
}
@Juggernaut .. Quick Union method is correct but it's sort of complicated when all we have to do is just count the number of connected components. Quick union will give who's the root node for each component etc. Such a matrix is a directed graph with nodes only in 2 directions (right and down). We simply need to run a BFS starting from top most position until all no more 1's can be reached. This will be 1 component. Now repeat the process, until ALL cells are discovered.
I used a simple two-dimensional array to solve this. I get an answer of 5 for the above case.
Also it traverses only once throughout the array.
public class FindShapes {
public FindShapes() {
super();
}
int[][] input={{1, 1, 0, 0, 1},
{1, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 1, 0, 0}};
public static void main(String[] args) {
FindShapes findShapes = new FindShapes();
System.out.println(findShapes.getShapes());
}
public int getShapes(){
boolean trigger=false;
int noOfShapes=0;
for(int i=0;i<input.length;i++){
for(int j=0;j<input[i].length;j++){
// System.out.println(i+"i j"+j+" "+input[i][j]);
if(input[i][j]==1){
trigger=true;
}else{
trigger=false;
}
if(trigger){
if((j+1)<input[i].length){
if(input[i][j+1]==1){
System.out.println("Shape in"+i+" "+j+" and "+i+" "+(j+1));
noOfShapes++;
trigger=false;
}
}
if((i+1)<input.length){
if(input[i+1][j]==1){
System.out.println("Shape in"+i+" "+j+" and "+(i+1)+" "+j);
noOfShapes++;
trigger=false;
}
}
}
}
}
return noOfShapes;
}
}
The solution is a variant of the 'quick find OR quick union'
1.) Use the input array as a data store or just clone it. (Space Complexity O(length * bredth)).
Use a 'counter = 1'
2.) for (each cell in array)
Check if the current cell has value 1. If yes, then,
2.1) Inspect the 4 surrounding cells to get the minimum value other than 1 or 0. Update the current cell and the surrounding 4 cells to that value. If no such value, then simply
update the cells including the current cell having value 1 to '++counter'
//At the end of the outer loop each cell will contain its 'group number + 1'.
3.) print out 'counter - 1' as the number of clusters.
Time complexity: O(n*m).
O(m*n)
public static int countShapes(int[][] a, int rows, int cols) {
int count = 0;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if (a[i][j] == 0) {
// do nothing
}
else if(
(i > 0 && a[i-1][j] == 2) ||
(i < rows-1 && a[i+1][j] == 2) ||
(j > 0 && a[i][j-1] == 2) ||
(j < cols-1 && a[i][j+1] == 2)
) {
a[i][j] = 2;
} else if (a[i][j] == 1) {
if ((i > 0 && j < cols-1 && a[i-1][j+1] == 2) &&
(j < cols-1 && a[i][j+1] == 1)) {
// do nothing
} else {
count++;
a[i][j] = 2;
}
}
}
}
return count;
}
#include <iostream>
using namespace std;
int test_matrix[4][5] = {1, 1, 0, 0, 1,1, 0, 0, 1, 0,1, 1, 0, 1, 0,0, 0, 1, 0, 0};
int test_matrix2[4][5] = {1, 1, 0, 0, 1,1, 0, 0, 1, 0,1, 1, 0, 1, 0,0, 0, 1, 1, 0};
int test_matrix3[4][5] = {1, 1, 1, 1, 1,1, 1, 0, 1, 1,1, 1, 0, 1, 1, 1, 1, 1, 1, 1};
void
findShape(int arr[][5], int row, int col) {
int shape = 0;
if(row == 0 || col == 0 ) return;
for (int i=0 ; i<row-1 ; i++) {
for (int j=0; j<col-1 ; j++) {
int r=i, c=j;
if (arr[i][j] && arr[i][j+1]) shape++;
if (arr[i][j] && arr[i+1][j]) shape++;
}
}
std::cout << "number of shape is " << shape << std::endl;
}
int main () {
findShape(test_matrix, 4, 5);
findShape(test_matrix2, 4, 5);
findShape(test_matrix3, 4, 5);
return 0;
}
val m = Array(Array(1, 1, 0, 0, 1),
Array(1, 0, 0, 1, 0),
Array(1, 1, 0, 1, 0),
Array(0, 0, 1, 0, 0))
def shapes(a: Array[Array[Int]]): Int = {
def count(r: Array[Int],acc: Int): Int = r match {
case Array() => acc
case Array(x,y@_*) if(x ==1) => val (a,b) = y.span(_ == 1)
if(a.length >= 1) perRow(b.toArray, acc+1) else perRow(b.toArray, acc)
case Array(_, y@_*) => perRow(y.toArray, acc)
}
val v = a.transpose
(a ++ v).foldLeft(0)((acc,r) => acc+ count(r, 0))
}
scala> val count = shapes(m)
count: Int = 4
Oops! copy pasted the wrong code. Here is the correct one:
def shapes(a: Array[Array[Int]]): Int = {
def count(r: Array[Int],acc: Int): Int = r match {
case Array() => acc
case Array(x,y@_*) if(x ==1) => val (a,b) = y.span(_ == 1)
if(a.length >= 1) count(b.toArray, acc+1) else count(b.toArray, acc)
case Array(_, y@_*) => count(y.toArray, acc)
}
val v = a.transpose
(a ++ v).foldLeft(0)((acc,r) => acc+ count(r, 0))
}
count_shape_lib.py
from sets import Set
class Matrix():
def __init__(self, matrix):
self.matrix = matrix
self.height = len(self.matrix)
self.width = len(self.matrix[0])
def get(self, point):
return self.matrix[point[0]][point[1]]
def valid_point(self, point):
if point[0] < self.height and point[0] >= 0 and point[1] < self.width and point[1] >= 0:
return True
else:
return False
def get_adjacent_points(self, point):
points = []
offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for offset in offsets:
tmp_point = (point[0]+offset[0], point[1]+offset[1])
if self.valid_point(tmp_point):
points.append(tmp_point)
return points
def points(self):
points = Set()
for i in range(self.height):
for j in range(self.width):
points.add((i, j))
return points
class Shape():
def __init__(self, matrix, seed):
self.matrix = matrix
self.seed = seed
self.shape_area = Set()
self.shape_area.add(seed)
self.boundry_area = Set()
self.probe_point(seed)
def probe_point(self, target_point):
changed = False
if self.matrix.get(target_point) == 1:
self.shape_area.add(target_point)
try:
self.boundry_area.remove(target_point)
except KeyError:
pass
for point in self.matrix.get_adjacent_points(target_point):
if point not in self.shape_area and point not in self.boundry_area:
self.boundry_area.add(point)
changed = True
return changed
def explore(self):
changed = True
while changed:
changed = False
target_points = list(self.boundry_area)
for point in target_points:
changed = self.probe_point(point) | changed
def points(self):
return self.shape_area + self.boundry_area
count_shapes_of_matrix.py
from count_shape_lib import *
matrix = Matrix([[1, 1, 0, 0, 1], [1, 0, 0, 1, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 0]])
shapes = []
untouched_points = matrix.points()
tmp_untouched_points = untouched_points.copy()
for point in tmp_untouched_points:
if matrix.get(point) == 0:
untouched_points.remove(point)
if untouched_points:
changed = True
while changed and untouched_points:
changed = False
for point in untouched_points:
shape = Shape(matrix, point)
shape.explore()
if shape.shape_area:
shapes.append(shape)
for point in shape.shape_area:
untouched_points.remove(point)
changed = True
break
print len(shapes)
If I read the question correctly, then any 1 that has a 1 on its left or above it is part of the same shape as that 1.
Therefore, only 1's with no 1 to the left or above are the start of a new shape. So just go through the array and count all the 1's with no 1 above or to the left, which we could check in O(N)?
int shapeCount = 0;
for(int i = 0; i < arr.len; i++)
{
for(int j = 0; i < arr[0].len; j++)
{
if(arr[i][j] == 1 && arr[i-1][j] != 1 && arr[i][j-1] != 1)
shapeCount++;
}
}
int[][] arr= {{1,1,0,0,1},{1,0,0,1,0},{1,1,0,1,0},{0,0,1,0,0}};
//int[][] arr= {{1,1,0,0,1},{1,0,0,1,0},{0,1,0,1,0},{0,0,1,1,0}};
//int[][] arr= {{1,1,0,0,1},{1,0,0,1,1},{1,1,0,1,0},{0,0,1,1,0}};
//int[][] arr= {{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1}};
//int[][] arr= {{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[0].length;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println(" ");
}
Boolean flag1= false;
Boolean flag2= false;
Boolean flag3= false;
int row = arr.length;
int col = arr[0].length;
int count=0;
for(int j=0;j<col;j++){
flag1=false;
for(int i=0;i<row;i++){
if(i==1){
if(arr[i][j]==1&&(arr[i-1][j]==1||arr[i+1][j]==1)){
count++;
flag1 = true;
}
}
if(i==2){
if(arr[i][j]==1&&(arr[i-1][j]==1||arr[i+1][j]==1)&&flag1==false){
count++;
}
}
}
}
for(int i=0;i<row;i++)
{
flag2=false;
flag3=false;
for(int j=0;j<col;j++)
{
if(j==1)
{
if(arr[i][j]==1&&(arr[i][j-1]==1||arr[i][j+1]==1))
{
count++;
flag2 = true;
flag3 = true;
}
}
if(j==2){
if(arr[i][j]==1&&(arr[i][j-1]==1||arr[i][j+1]==1)&&flag2==false)
{
count++;
flag3=true;
}
}
if(j==3)
{
if(arr[i][j]==1&&(arr[i][j-1]==1||arr[i][j+1]==1)&&flag3==false)
count++;
}
}
}
System.out.println("Count "+count);
System.out.println("Row "+row);
System.out.println("Column "+col);
/*result = searchNumber(arr,70,col,row);
System.out.println(result);
*/
}
}
its working in all cases
public class Seq
{
public static boolean searchNumber(int[][] a,int number,int column,int row){
// for unwanted/out of range input
if(number < a[0][0] || number > a[row-1][column-1])
return false;
for(int i=0;i<row-1;i++)
{
//Increament row number for finding the element
for(int j=column-1;j>=0;j--)
{
// check the element at ith row an jth column is less
//than given number
if(a[i][j]<number)
break;
//check if both are same
else if(a[i][j]==number)
return true;
//else the number will be less than a[i][j],
//so decrement the column by j--
}
}
// if not found, return false
return false;
}
public static void main(String args[])
{
//int[][] arr= {{1,1,0,0,1},{1,0,0,1,1},{1,1,0,1,0},{0,0,1,1,0}};
//int[][] arr= {{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1}};
int[][] arr= {{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
for(int i=0;i<arr.length;i++)
{
for(int j=0;j<arr[0].length;j++)
{
System.out.print(arr[i][j]+" ");
}
System.out.println(" ");
}
Boolean result = false;
int row = arr.length;
int col = arr[0].length;
int j,i,count1 = 0,count2 = 0;
for(i = 0;i<=row-1;i++)
{
for(j = 1; j<=col-1;j++)
{
int num = (arr[i][j-1] & arr[i][j]);
System.out.print(num);
if((arr[i][j-1] & arr[i][j])==1)
{
count1++;
if(j+1<=col-1)
{
if(((arr[i][j-1] & arr[i][j])+(arr[i][j] & arr[i][j+1]))==2)
count1--;
}
}
}
System.out.println("");
}
System.out.println("\n\n");
for(i = 1;i<=row-1;i++)
{
for(j = 0; j<=col-1;j++)
{
int num = (arr[i-1][j] & arr[i][j]);
System.out.print(num);
if((arr[i-1][j] & arr[i][j])==1)
{
count2++;
if(i+1<=row-1)
{
if(((arr[i-1][j] & arr[i][j])+(arr[i][j] & arr[i+1][j]))==2)
{
count2--;
}
}
}
}
System.out.println("");
}
System.out.println("TOTAL COUNT = "+(count1+count2));
System.out.println("Row "+row);
System.out.println("Column "+col);
//result = searchNumber(arr,10,col,row);
//System.out.println(result);
}
}
Using the breadcrumbs method, I created another matrix with O(M) space complexity.
def shapeCounter(matrix):
count = 0
counter = [[0]*len(matrix[0])]*len(matrix[0])
def countHelper(row,col,count):
withinBounds = row<len(matrix) and col<len(matrix[0])
if withinBounds:
isFilled = matrix[row][col]
if isFilled:
counter[row][col] = 1
countHelper(row+1, col, count)
countHelper(row, col+1, count)
for rowIndex, row in enumerate(matrix):
for colIndex, element in enumerate(row):
if matrix[rowIndex][colIndex] == 1 and counter[rowIndex][colIndex]==0:
count += 1
countHelper(rowIndex,colIndex,count)
print count
f = open('input.txt')
matrix = []
for line in f:
line_array = line.split(' ')
line_array = line_array[:len(line_array)-1]
line_array = map(lambda x: 1 if x=='1' else 0, line_array)
matrix.append(line_array)
shapeCounter(matrix)
Its so lame I feel like laughing
How about :
if ( a[i][j] == 1 && a[i-1][j] != 1 && a[i][j-1] != 1 ) // insert boundry conditions
count++;
Ok, now here's the correct answer. space complexity ( using the same matrix ). time complexity ( O(m*n) ).
Traverses the matrix only once. method : breadcrumbs
I guess that is the best.
private static int countIslands(int[][] matrix) {
int count=0;
for ( int i=0 ; i<matrix.length ; i++ ){
for ( int j=0 ; j<matrix[i].length ; j++){
if ( matrix[i][j] == 1 ){
if ( (i>0?matrix[i-1][j]==0:true) && (j>0?matrix[i][j-1]==0:true)){
matrix[i][j]=-1;
count++;
}else{
matrix[i][j]=-2;
if ( i>0 && j>0 ){
if ( matrix[i][j-1] == -1){
if ( matrix[i-1][j] == -1 ){
matrix[i-1][j] = -2;
count--;
} else if ( matrix[i-1][j] == -2 ){
matrix[i][j-1] = -2;
count--;
}
}else if ( matrix[i][j-1] == -2 && matrix[i-1][j] == -1 ){
matrix[i-1][j] = -2;
count--;
}
}
}
}
}
}
return count;
}
#include <stdio.h>
#define MAX 5
#define MAX1 4
int main(int argc, char const *argv[])
{
int a[MAX][MAX1];
int i,j;
for (i = 0; i < MAX; ++i)
{
for (j = 0; j < MAX1; ++j)
{
a[i][j]=rand()%2;
printf("%d ",a[i][j] );
}
printf("\n");
}
printf("\n");
int count=0;
for (i = 0; i < MAX; ++i)
{
for (j = 0; j < MAX1; ++j)
{
if(a[i][j]==1)
{
if(j!=MAX1)
{
switch(a[i][j+1])
{
case 1:
a[i][j]=a[i][j+1]=2;
count++;
break;
case 2:
printf("some error here %d %d",i,j);
break;
case 3:
a[i][j]=2;
a[i][j+1]=4;
count++;
break;
case 4:break;
}
}
if(i!=MAX)
{
switch(a[i+1][j])
{
case 1:
a[i][j]=a[i+1][j]=3;
count++;
break;
case 2:
a[i][j]=3;
a[i+1][j]=4;
count++;
break;
case 3:
printf("some problem %d %d\n",i,j);
break;
case 4:
break;
}
}
}
else if(a[i][j]==2)
{
if(j!=MAX1)
{
switch(a[i][j+1])
{
case 1:
a[i][j]=a[i][j+1]=2;
break;
case 2:
printf("some error here %d %d",i,j);
break;
case 3:
a[i][j]=2;
a[i][j+1]=4;
count++;
break;
case 4:break;
}
}
if(i!=MAX)
{
switch(a[i+1][j])
{
case 1:
a[i][j]=4;
a[i+1][j]=3;
count++;
break;
case 2:
// a[i][j]=3;
// a[i+1][j]=4;
break;
case 3:
a[i][j]=2;
a[i][j+1]=4;
count++;
break;
case 4:
break;
}
}
}
else if(a[i][j]==3)
{
if(j!=MAX1)
{
switch(a[i][j+1])
{
case 1:
a[i][j]=4;
a[i][j+1]=3;
count++;
break;
case 2:
printf("some error here %d %d",i,j);
break;
case 3:
break;
case 4:break;
}
}
if(i!=MAX)
{
switch(a[i+1][j])
{
case 1:
a[i][j]=4;
a[i+1][j]=3;
break;
case 2:
// a[i][j]=3;
// a[i+1][j]=4;
break;
case 3:
a[i][j]=2;
a[i][j+1]=4;
break;
case 4:
break;
}
}
}
printf("%d ",a[i][j] );
}
printf("\n");
}
printf("%d \n",count );
return 0;
}
This is an N-squared solution. Every element in the matrix gets visited a maximum of five times.
- showell30@yahoo.com February 18, 2013# In this solution as soon as we find a 1, we replace # all the elements in the shape with 2 to avoid double # counting the 1s. Otherwise, it's simple iteration. def count_shapes(m): num_shapes = 0 for r in range(len(m)): for c in range(len(m[0])): if m[r][c] == 1: fill_shape_with_twos(m, r, c) num_shapes += 1 # restore the original values for r in range(len(m)): for c in range(len(m[0])): m[r][c] = m[r][c] / 2 return num_shapes def fill_shape_with_twos(m, r, c): m[r][c] = 2 if r > 0 and m[r-1][c] == 1: fill_shape_with_twos(m, r-1, c) if r + 1 < len(m) and m[r+1][c] == 1: fill_shape_with_twos(m, r+1, c) if c > 0 and m[r][c-1] == 1: fill_shape_with_twos(m, r, c-1) if c + 1 < len(m[0]) and m[r][c+1] == 1: fill_shape_with_twos(m, r, c+1) test_matrix = [ [1, 1, 0, 0, 1], [1, 0, 0, 1, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 0], ] test_matrix2 = [ [1, 1, 0, 0, 1], [1, 0, 0, 1, 0], [1, 1, 0, 1, 0], [0, 0, 1, 1, 0], ] test_matrix3 = [ [1, 1, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1], ] print count_shapes(test_matrix) print count_shapes(test_matrix2) print count_shapes(test_matrix3)