Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # ------------------- fast io --------------------
- import os
- import sys
- from io import BytesIO, IOBase
- BUFSIZE = 8192
- class FastIO(IOBase):
- newlines = 0
- def __init__(self, file):
- self._fd = file.fileno()
- self.buffer = BytesIO()
- self.writable = "x" in file.mode or "r" not in file.mode
- self.write = self.buffer.write if self.writable else None
- def read(self):
- while True:
- b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
- if not b:
- break
- ptr = self.buffer.tell()
- self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
- self.newlines = 0
- return self.buffer.read()
- def readline(self):
- while self.newlines == 0:
- b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
- self.newlines = b.count(b"\n") + (not b)
- ptr = self.buffer.tell()
- self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
- self.newlines -= 1
- return self.buffer.readline()
- def flush(self):
- if self.writable:
- os.write(self._fd, self.buffer.getvalue())
- self.buffer.truncate(0), self.buffer.seek(0)
- class IOWrapper(IOBase):
- def __init__(self, file):
- self.buffer = FastIO(file)
- self.flush = self.buffer.flush
- self.writable = self.buffer.writable
- self.write = lambda s: self.buffer.write(s.encode("ascii"))
- self.read = lambda: self.buffer.read().decode("ascii")
- self.readline = lambda: self.buffer.readline().decode("ascii")
- sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
- input = lambda: sys.stdin.readline().rstrip("\r\n")
- # ------------------- fast io --------------------
- import sys
- sys.setrecursionlimit(10**6)
- def check(cnt, cnt2):
- # 7 5
- x,y = min(cnt, cnt2), max(cnt, cnt2)
- if x < 2:return 0
- # find greatest x such that 2x <= y
- k = max(0, min(y//2, x) - 1) + max(0, min(x//2, y) - 1)
- return k
- for _ in range(int(input()) if True else 1):
- cs = "Case #"+str(_ + 1)+":"
- # n = int(input())
- n, m = map(int, input().split())
- # a, b = map(int, input().split())
- # c, d = map(int, input().split())
- # a = list(map(int, input().split()))
- # b = list(map(int, input().split()))
- a = []
- for i in range(n):
- a += [list(map(int, input().split()))]
- left = [[-1]*m for i in range(n)]
- right = [[-1]*m for i in range(n)]
- def checkright(i, j):
- if not 0 <= j < m:return 0
- if right[i][j] == -1:
- if a[i][j] == 0:
- right[i][j] = 0
- else:
- right[i][j] = 1 + checkright(i, j+1)
- return right[i][j]
- def checkleft(i, j):
- if not 0 <= j < m:return 0
- if left[i][j] == -1:
- if a[i][j] == 0:
- left[i][j] = 0
- else:
- left[i][j] = 1 + checkleft(i, j-1)
- return left[i][j]
- ans = 0
- cnt = 0
- for j in range(m):
- cnt = 0
- for i in range(n):
- if a[i][j] == 1:
- cnt += 1
- else:
- cnt = 0
- if cnt >= 2:
- ans += check(cnt, checkright(i,j)) + check(cnt, checkleft(i, j))
- for j in range(m):
- cnt = 0
- for i in range(n - 1, -1, -1):
- if a[i][j] == 1:
- cnt += 1
- else:
- cnt = 0
- if cnt >= 2:
- ans += check(cnt, checkright(i,j)) + check(cnt, checkleft(i, j))
- print(cs+" " +str(ans))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement