-
Notifications
You must be signed in to change notification settings - Fork 1
/
Connected Cells in a Grid.clj
54 lines (48 loc) · 1.41 KB
/
Connected Cells in a Grid.clj
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
(ns connected-cells
(:import (java.util Scanner)))
(defn get-neighbors [[i j]]
(for [f [identity dec inc]
g [identity dec inc]
:when (not= f g identity)]
[(f i)
(g j)]))
(defn lookup [arr t1 t2]
(= (get-in arr t1)
(get-in arr t2)))
(defn flood-fill
([arr target]
(loop [q (conj (clojure.lang.PersistentQueue/EMPTY) target)
visited #{}]
(if (empty? q)
visited
(let [c (peek q)
unv (->> c
get-neighbors
(remove visited)
(filter #(lookup arr target %)))]
(recur (pop (into q unv))
(conj visited c)))))))
(defn find-max-region
([arr m n]
(reduce (fn [[mx visited] t]
(if (or (not= (get-in arr t) 1) (visited t))
[mx visited]
(let [v (flood-fill arr t)]
[(max mx (count v))
(into visited v)])))
[0 #{}]
(for [i (range m)
j (range n)]
[i j])))
([arr]
(find-max-region arr (count arr) (count (arr 0)))))
(defn -main []
(let [scan (Scanner. *in*)
m (.nextInt scan)
n (.nextInt scan)
vv (doall (mapv (fn [_] (mapv
(fn [_] (.nextInt scan))
(range n)))
(range m)))]
(println (first (find-max-region vv)))))
(-main)