Posted By

cb9 on 06/26/11

Tagged

Versions (?)

Last Edited at 06/26/11 07:55am

Statistics

Viewed 714 times

Favorited by 0 user(s)

Related snippets

Find \"Square\" of 1s in a 2D Array of 1s and 0s.

/ Published in: C#

Highlighted TextExpand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace C9Test
{
    class Program
    {
        static void Main(string[] args)
        {
            int width = 6, length = 5;
            int[][] arr = new int[length][];

arr[0] = new int[] { 1, 1, 1, 0, 1, 1 };
            arr[1] = new int[] { 1, 1, 1, 1, 1, 1 };
            arr[2] = new int[] { 1, 1, 1, 1, 1, 1 };
            arr[3] = new int[] { 0, 0, 1, 1, 1, 1 };
            arr[4] = new int[] { 0, 0, 1, 1, 1, 1 };

/*
            //After run 1
            { 1, 1, 0, 0, 1, 0 }
            { 1, 1, 1, 1, 1, 0 }
            { 0, 0, 1, 1, 1, 0 }
            { 0, 0, 1, 1, 1, 0 }
            { 0, 0, 0, 0, 0, 0 }

//After run 2
            { 1, 0, 0, 0, 0, 0 }
            { 0, 0, 1, 1, 0, 0 }
            { 0, 0, 1, 1, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }

//After run 3
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 1, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            
            //After run 4
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
            { 0, 0, 0, 0, 0, 0 }
       
            */

int size = 1;
            do
            {
                var newarr = SetMask(arr, width, size);
                var hasone = newarr.Count(y => y.Any(x => x == 1));
                if (hasone == 0)
                {
                    break;
                }
                else
                {
                    size++;
                    arr = newarr;
                }
            }
            while (true);

if (size > 1)
            {
                var rowhasones = arr.Select((r, i) => new { Index = i, RowData = r })
                                    .Where(y => y.RowData.Any(x => x == 1))
                                    .Select(r => r.Index);

foreach (var rowindex in rowhasones)
                {
                    for (int i = 0; i < width; i++)
                    {
                        if (arr[rowindex][i] == 1)
                        {
                            Console.WriteLine("{0:d}x{0:d} square @ ({1:d},{2:d})", size, rowindex, i);
                        }
                    }
                }

}
        }

static int[][] SetMask(int[][] arrSrc, int width, int offset)
        {
            var length = arrSrc.Length;
            var maxlencheck = length - offset;
            var arrRet = new int[length][];
            for (int i = 0; i < length; i++)
            {
                arrRet[i] = new int[width]; //default to zeroes
            }

//Project to anonymous type to get array index
            var rowhasones = arrSrc.Select((r, i) => new { Index = i, RowData = r })
                                .Where((r, i) => i < maxlencheck && r.RowData.Any(x => x == 1))
                                .Select(r => r.Index)
                                .OrderBy(i => i);

foreach (var rowindex in rowhasones)
            {
                if (rowindex == maxlencheck)
                {
                    //last row is all zeroes
                    continue;
                }

var currow = arrSrc[rowindex];
                var nextrow = arrSrc[rowindex + 1];
                var maxcolcheck = width - offset;
                
                for (int i = 0; i < maxcolcheck; i++)
                {
                    if (currow[i] == 1 && currow[i + 1] == 1 && nextrow[i] == 1 && nextrow[i + 1] == 1)
                    {
                        arrRet[rowindex][i] = 1;
                    }
                }
            }
            return arrRet;
        }
    }
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.