Find the haystack in the needles

Question

In a twist on finding a needle in a haystack, you need to find the largest contiguous haystack containing exactly one needle. Note that you cannot connect cells on diagonals, only left/right/up/down.

Input

An array (or a number of user input lines, your pick) of 'N' (needles) and '#' (hay) characters. Input only contains those two characters, and must contain at least one of each. For example:

N#N#N
#NN##
###N#
N##N#

Output

The size of the largest possible valid haystack. For our example, we would output 11 (there are 11 pieces of hay, and one needle).

   # 
#  ##
###N#
 ## #

This is code-golf, so shortest code wins. Standard loophole restrictions apply.

Test Cases

Input on left, possible maximal haystack on right

Case 1: 4

N##    ##
NN#     #
#NN     N
#N#     #

Case 2: 7

###   ###
N#N    # 
NNN    N 
###   ###

Case 3: 10

N###N    ### 
#N#N#   #N#  
#N#N#   # #  
N###N    ###

Case 4: 10

N#N#N        
#N#N#   # # #
##N##   ##N##
#N#N#   # # #
N#N#N        

Case 5: 1

NN#NN        
NNNNN         
#NNN#   #N    
NN#NN        

Answer 1

JavaScript (ES6), 152 bytes

s=>[...s].map((n,i)=>n>'M'&&(a=[...s],a[i]=r=1,a.map(_=>a.map((c,j)=>c=='#'&&a[j+1]|a[j-1]|a[j+l]|a[j-l]?a[j]=++r:0)),o=r>o?r:o),o=0,l=~s.search`
`)|o-1

Explanation

For each needle in the input, sets the needle to a part of the haystack (represented by setting it to a non-zero number) and continuously checks hay cells. If hay contains an adjacent part of the hay stack, also sets it part of the haystack and increments the size of the hay stack. Outputs the highest result.

var solution =

s=>
  [...s].map((n,i)=>n>'M'&&(          // for each needle in s at index i
      a=[...s],                       // a = array of each character in s
      a[i]=1,                         // set the starting needle to 1 (haystack)
      r=0,                            // r = haystack size starting from this needle
      a.map(_=>                       // loop to ensure the complete haystack is found
        a.map((c,j)=>                 // for each cell c at index j
          c=='#'&&                    // if the current cell is hay
          a[j+1]|a[j-1]|a[j+l]|a[j-l] // and any adjacent cells are part of the haystack
          ?a[j]=++r:0                 // add the current cell to the haystack, increment r
        )
      ),
      o=r>o?r:o                       // o = max of o and r
    ),
    o=0,                              // o = final output, initialise to 0
    l=~s.search`
`                                     // l = line length of s
  )
  |o                                  // return o

<textarea id="input" rows="6" cols="40">N#N#N
#N#N#
##N##
#N#N#
N#N#N</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

Answer 2

Ruby, 207

->a{d=->b{0...b.size}
f=c=s=->y,x{(d[a]===y&&d[a[0]]===x&&!f[y][x]&&a[y][x]==c)?(c,f[y][x]=?#,1
1+s[y,x-1]+s[y,x+1]+s[y-1,x]+s[y+1,x]):0}
d[a].map{|y|d[y].map{|x|f,c=a.map{|b|b.map{p}},?N
s[y,x]}.max}.max-1}

This is an anonymous function that takes in the input as an array of arrays. Usage:

f=->a{......}

f["
N##
NN#
#NN
#N#
".strip.split.map(&:chars)] # => 4

The proc named s recursively finds the size of the haystack with needle at specific coordinates and is called on each needle in the haystack.

Answer 3

Python3, 285 bytes

Similar to the other solutions, the code below builds haystacks by first anchoring the search on each needle present in the input.

E=enumerate
def G(x,y,d):
 q,s=[(x,y)],[(x,y)]
 for x,y in q:
  t=[u for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]if d.get(u:=(x+X,y+Y))and u not in s and'#'==d[u]]
  q+=t;s+=t
 return s
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)}
 return max([G(*i,d)for i in d if'N'==d[i]],key=len)

Try it online!

Python3, 559 bytes

Out of academic curiosity, the solution below finds all possible haystacks with a needle, and then selects the largest. This approach is exactly the opposite of the code above and the other answers.

E=enumerate
def f(b):
 d,P={(x,y):v for x,r in E(b)for y,v in E(r)},[]
 q=[([t:=[i for i in d if'#'==d[i]][0]],[t],[],0)]
 for s,S,g,c in q:
  if[]==s:
   if[]==(k:=[i for i in d if i not in[J for K in g+[S]for J in K]and'#'==d[i]]):P+=g+[S]
   if k:q+=[(k[:1],k[:1],g+[S],0)]
   continue
  (x,y),*s=s
  L=[[],[]]
  for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]:
   if d.get(u:=(x+X,y+Y))and u not in S:L[d[u]=='#']+=[u]
  for i in L[0]*(0==c):q+=[(s+L[1]+[i],S+L[1]+[i],g,1)]
  q+=[(s+L[1],S+L[1],g,c)]
 return max([i for i in P if any(d[j]=='N'for j in i)],key=len)

Try it online!