07. Largest area in matrix


0

Здравейте,

Имам въпрос относно Time Limt за тази задача от домашното. Моето решение дава 30/100, като са ми правилни първите 3 теста и на останалите надминавам допустимото време. Ето го моето решение:

using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace LargestArea { class LargestArea { static void Main() { int seqMax = int.MinValue; int seqCurrent = 0; //take dimensions string[] rc = Console.ReadLine().Split(' '); int rown = int.Parse(rc[0]); int coln = int.Parse(rc[1]); int[,] matrix = new int[rown,coln]; bool[,] mark = new bool[rown, coln]; Queue<int> filer = new Queue<int>(); Queue<int> filec = new Queue<int>(); //take matrice for (int r = 0; r < rown; r++) { rc = Console.ReadLine().Split(' '); for (int c = 0; c < coln; c++) { matrix[r, c] = int.Parse(rc[c]); } } int curr = 0; int curc = 0; for (int r = 0; r < rown; r++) { for (int c = 0; c < coln; c++) { filer.Enqueue(r); filec.Enqueue(c); mark[r,c] = true; seqCurrent = 1; while (filer.Count > 0) { curr = filer.Peek(); curc = filec.Peek(); filer.Dequeue(); filec.Dequeue(); //neighbours //right if (curc + 1 < coln && mark[curr, curc + 1] == false) { if (matrix[curr, curc + 1] == matrix[r, c]) { filer.Enqueue(curr); filec.Enqueue(curc + 1); mark[curr, curc + 1] = true; seqCurrent++; } } //down if (curr + 1 < rown && mark[curr + 1, curc] == false) { if (matrix[curr + 1, curc] == matrix[r, c]) { filer.Enqueue(curr + 1); filec.Enqueue(curc); mark[curr + 1, curc] = true; seqCurrent++; } } //left if (curc - 1 >= 0 && mark[curr, curc - 1] == false) { if (matrix[curr, curc - 1] == matrix[r, c]) { filer.Enqueue(curr); filec.Enqueue(curc - 1); mark[curr, curc - 1] = true; seqCurrent++; } } //up if (curr - 1 > 0 && mark[curr - 1, curc] == false) { if (matrix[curr - 1, curc] == matrix[r, c]) { filer.Enqueue(curr - 1); filec.Enqueue(curc); mark[curr - 1, curc] = true; seqCurrent++; } } } if (seqMax < seqCurrent) { seqMax = seqCurrent; } Array.Clear(mark, 0, mark.Length); } } Console.WriteLine(seqMax); } } }

Как мога да подобря скоростта на изпълнението?

Когато BGcoder дава грешка за времето означава ли, че отговора е правилен, но времето за изпълнение е по-дълго или след като времето за изпълнение е по-дълго въобще не се проверява отговора?




Отговори



0

Намерих си грешката.

Не трябваше да инициализирам булевата матрица, която ми пази посетените стойности след while цикъла. По този начин от всяка стойност алгоритъма проверяваше цялата матрица на ново.


от perro (7 точки)


0
Можеш ли да покажеш къде точно ти е грешката в кода? 

от SPENS03 (82 точки)