Breadth-First Search Algorithm
This is the problem set and as you can see there’s a hint which I used. To be exact – I found this video on youtube. It may no look like much but for me it was very educative.
So I start with a hardcoded array numbers[n,m]. I make an array of the same size but of type char visited[n,m], in which if numbers[row,col] visited => visited[row,col]='y'. That way I know where I have already visited and won't go again. Also I have an array of two rows and all of the numbers' elements (i.e. row*col) in which I store the indexes of the cells I need to visit.
First step
Take an element with indexes rowStarting and colStarting. If visited go to next element.
Second step
If its the first step of a new element-type->Take colChecked = colStarting and rowChecked=colStarting. This is the first element and it's always equal to itself so currentSum++ (==1) . OtherwiseNext take rowChecked and colChecked and check it with the starting symbol.And put current cell indexes in visited[rowChecked,colChecked] = 'y' from queue I check if up,down,left or right is the same element and if it is not visited I put it in the queue. Next, if queue is not empty I take the last element from it(indexes of next cell to visit). Visit that cell ...Repeat second step until there are no more elements in queue.
Third step
Check if the current sum is grater than maximal sum and give maxSum=currentSum if so. Next i repeat First Step. Until there are no more elements left unvisited - And - The End
The Code
PasteBin or here:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
//* Write a program that finds the largest area of equal neighbor//elements in a rectangular matrix and prints its size. Example://1 3 2 2 2 4//3 3 3 2 4 4//4 3 1 2 3 3//4 3 1 3 3 1//4 3 3 3 1 1using System;class AreaOfNeighbouringElements{ static void Main(string[] args) { int[,] numbers = { { 1, 3, 2, 2, 2, 4 ,9, 9, 9, 2, 4 }, { 3, 3, 3, 2, 4, 4 ,9, 3, 9, 4, 4 }, { 4, 3, 1, 2, 3, 3 ,9, 1, 9, 3, 3 }, { 4, 3, 1, 4, 9, 3 ,9, 1, 9, 3, 3 }, { 4, 3, 3, 3, 9, 3 ,9, 3, 9, 3, 3 }, { 4, 3, 3, 3, 9, 3 ,9, 1, 9, 3, 3 }, { 4, 3, 3, 3, 9, 9 ,9, 1, 2, 9, 9 }, { 4, 3, 3, 3, 3, 3 ,3, 1, 2, 3, 9 }, }; int queueLenght = numbers.GetLength(0) * numbers.GetLength(1); int queueIndex = -1; char[,] visited = new char[numbers.GetLength(0), numbers.GetLength(1)]; int[,] queue = new int[2, queueLenght]; for (int i = 0; i < queue.GetLength(0); i++) { for (int y = 0; y < queue.GetLength(1); y++) { queue[i, y] = -1; } } //int nextLeft = 0, nextRight = 0, nextUp = 0, nextDown = 0; int currentSize = 0, maxSize = 0, rowChecked = 0, colChecked = 0; for (int rowStarting = 0; rowStarting < numbers.GetLength(0); rowStarting++) { for (int colStarting = 0; colStarting < numbers.GetLength(1); colStarting++) { // if already visited = get next if (visited[rowStarting,colStarting]=='y') { continue; } //get nex type of element i.e. utill now was '1' next is '3' rowChecked = rowStarting; colChecked = colStarting; do { //check if current is as the first if (numbers[rowStarting, colStarting] == numbers[rowChecked, colChecked] && visited[rowChecked, colChecked] != 'y') { currentSize++; //put in the same row and col of array "visited an 'y'" //so we don't check(use it as starting element) it again visited[rowChecked, colChecked] = 'y'; //check upper and put in queue if equal and not visited already if (rowChecked - 1 >= 0) { if (numbers[rowChecked - 1, colChecked] == numbers[rowStarting, colStarting] && visited[rowChecked - 1, colChecked] != 'y') { queueIndex++; queue[0, queueIndex] = rowChecked - 1; queue[1, queueIndex] = colChecked; } } //check down - add to queue if not visited already if (rowChecked + 1 < numbers.GetLength(0)) { if (numbers[rowChecked + 1, colChecked] == numbers[rowStarting, colStarting] && visited[rowChecked + 1, colChecked] != 'y') { queueIndex++; queue[0, queueIndex] = rowChecked + 1; queue[1, queueIndex] = colChecked; } } //check left - add to queue if not visited already if (colChecked - 1 >= 0) { if (numbers[rowChecked, colChecked - 1] == numbers[rowStarting, colStarting] && visited[rowChecked, colChecked - 1] != 'y') { queueIndex++; queue[0, queueIndex] = rowChecked; queue[1, queueIndex] = colChecked - 1; } } //check right - add to queue if not visited already if (colChecked + 1 < numbers.GetLength(1)) { if (numbers[rowChecked, colChecked + 1] == numbers[rowStarting, colStarting] && visited[rowChecked , colChecked + 1] != 'y') { queueIndex++; queue[0, queueIndex] = rowChecked; queue[1, queueIndex] = colChecked + 1; } } } //if there are any elements in queue and they are //valid array index identifiers i.e. not -1 but 0,1,2,3.... if (queueIndex > -1&&queue[0,queueIndex]!=-1) { //take the row and col from queue and give -1 //to the queue - delete the queue entry rowChecked = queue[0, queueIndex]; queue[0, queueIndex] = -1; colChecked = queue[1, queueIndex]; queue[1, queueIndex] = -1; queueIndex--; } else { break; } } while (queueIndex > -2); if (currentSize>maxSize) { maxSize = currentSize; } currentSize = 0; } } Console.WriteLine(maxSize); }} |
It’s allowed to leave a comment
Good example.
Adding my two cents – instead of using the array queue – you can use the generic Queue.
Add a new structure “rowColumn”
struct rowColumn
{
public int row;
public int col;
};
then replace the array queue with generic Queue
//int[,] queue = new int[2, queueLenght];
Queue _queue = new Queue(queueLenght);
/*for (int i = 0; i < queue.GetLength(0); i++)
{
for (int y = 0; y = 0)
{
if (numbers[rowChecked - 1, colChecked] == numbers[rowStarting, colStarting] && visited[rowChecked - 1, colChecked] != ‘y’)
{
//queueIndex++;
//queue[0, queueIndex] = rowChecked – 1;
//queue[1, queueIndex] = colChecked;
rowColumn rc = new rowColumn();
rc.row = rowChecked-1;
rc.col = colChecked;
_queue.Enqueue(rc);
}
}
similarly in other location where the array queue is
Modify the if condition on the array queue.
/*if (queueIndex > -1 && queue[0, queueIndex] != -1)
{
//take the row and col from queue and give -1
//to the queue – delete the queue entry
Console.WriteLine(“found neighbor for Row and Column {0},{1}”, rowChecked, colChecked);
//rowChecked = queue[0, queueIndex];
queue[0, queueIndex] = -1;
//colChecked = queue[1, queueIndex];
queue[1, queueIndex] = -1;
queueIndex–;
}*/
if (_queue.Count > 0)
{
Console.WriteLine(“found neighbor for Row and Column {0},{1}”, rowChecked, colChecked);
rowColumn rc = _queue.Dequeue();
rowChecked = rc.row;
colChecked = rc.col;
}
It’s a good idea. I’ll try it as soon as I get some time. thx