Skip to main content

Return to Answer

Syntax highlight
Source Link
Eric
Eric
  • 98.1k
  • 54
  • 257
  • 389
#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t)) 
#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t)) 
#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t)) 
#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))
added 1 character in body
Source Link
tommy.carstensen
tommy.carstensen
  • 9.7k
  • 15
  • 70
  • 112

Here is a PythonPython3 solution, which returns the position in addition to the area of the largest rectangle:

#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))

Output:

area 12 Cell 1:(2, 1) and Cell 2:(4, 4)

Here is a Python solution, which returns the position in addition to the area of the largest rectangle:

#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))

Output:

area 12 Cell 1:(2, 1) and Cell 2:(4, 4)

Here is a Python3 solution, which returns the position in addition to the area of the largest rectangle:

#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))

Output:

area 12 Cell 1:(2, 1) and Cell 2:(4, 4)
Source Link
tommy.carstensen
tommy.carstensen
  • 9.7k
  • 15
  • 70
  • 112

Here is a Python solution, which returns the position in addition to the area of the largest rectangle:

#!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t))

Output:

area 12 Cell 1:(2, 1) and Cell 2:(4, 4)