Problem:


尾根 (Ridge)

問題

JOI カルデラは景観の良さが多くの登山家に愛される美しい地形である．
特に，尾根と呼ばれる場所からの景観は絶景である．

JOI カルデラの土地は南北 H キロメートル，東西 W キロメートルの長方形である．
南北，東西に 1 キロメートルごとに JOI カルデラの土地を分け，これら H×W 個の領域を区域と呼ぶ．
すべての区域において，その中では標高は等しい．また，異なる区域の標高は異なる．

ある区域に雨が降ると，雨水はその区域に東西南北に隣り合う最大で 4 つの区域のうち，
標高がその区域より低いような区域のすべてに流れる．そのような区域がない場合，雨水はその区域に溜まる．
他の区域から流れてきた雨水についても同様である．
JOI カルデラの外側は，外輪山の急峻な崖に囲まれているため，雨水が JOI カルデラの外に流れ出すことはない．

ある区域について，その区域のみに雨が降った場合，最終的に複数の区域に雨水が溜まるとき，その区域を尾根と呼ぶ．
絶景をこよなく愛する登山家たちのために，尾根の区域がいくつあるかを求めるプログラムを作成せよ．

入力

入力は 1 + H 行からなる．

1 行目には 2 個の整数 H, W (1 ≦ H ≦ 1000, 1 ≦ W ≦ 1000) が空白を区切りとして書かれており，JOI カルデラが南北に H キロメートル，東西に W キロメートルにわたることを表す．

続く H 行にはそれぞれ W 個の整数が空白を区切りとして書かれており，標高の情報を表す．
H 行のうちの i 行目の j 番目 (1 ≦ i ≦ H, 1 ≦ j ≦ W) の整数 Mi,j (1 ≦ Mi,j ≦ H×W) は，JOI カルデラの北から i 行目，西から j 列目の区域の標高を表す．
(i,j) ≠ (k,l) なら，Mi,j ≠ Mk,l を満たす．

出力

尾根の区域の個数を 1 行で出力せよ．

入出力例

入力例 1

3 3
2 9 4
7 5 3
6 1 8

出力例 1

   

4

入力例 2

  

3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15

出力例 2

  

4

入力例 1 において，標高が 5, 7, 8, 9 の 4 個の区域が尾根である．例えば，標高 9 の区域に雨が降った場合，最終的に雨水は標高 1, 2, 3 の 3 個の区域に溜まる．したがって，標高 9 の区域は尾根である．また，標高 6 の区域に雨が降った場合，最終的に雨水は標高 1 の区域にしか溜まらない．したがって，標高 6 の区域は尾根ではない．

入力例 2 において，標高が 8, 10, 11, 12 の 4 個の区域が尾根である．

情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』



Sample input:
3 3
2 9 4
7 5 3
6 1 8


Sample output:
4

Submission status: Wrong Answer

Solution code:
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w=map(int,raw_input().split())
g=[map(int,raw_input().split()) for _ in xrange(h)]
pos=[-1]*(h*w)
for i in xrange(h):
    for j in xrange(w):
        pos[g[i][j]-1]=[i,j]

dy=(1,0,-1,0)
dx=(0,1,0,-1)
stop=[set() for _ in xrange(h*w)]
ans=0
for i in xrange(h*w):
    y,x=pos[i]
    for j in xrange(4):
        ny=y+dy[j];nx=x+dx[j]
        if check(ny,nx):
            if g[ny][nx]<g[y][x]:
                stop[i]=stop[i]|stop[g[ny][nx]-1]
    cnt=len(stop[i])
    if cnt>=2:
        ans+=1
    elif cnt==0:
        stop[i].add(g[y][x])

Submission status: Wrong Answer

Solution code:
def main():
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    H,W = map(int,input().split())
    a = [ list(map(int,input().split())) for _ in range(H) ]
    b = [ W*[-1] for _ in range(H) ]
    arr = []
    for y in range(H):
        for x in range(W):
            arr.append((a[y][x],x,y))
    arr = sorted(arr)
    ans = 0
    for i in range(len(arr)):
        x,y = arr[i][1], arr[i][2]
        b[y][x] = 0
        for j in 4*[0]:
            nx = x + dx[j]
            ny = y + dy[j]
            if not ( ( 0 <= nx and nx < W ) and ( 0 <= ny and ny < H ) ):
                continue
            if b[ny][nx] != -1:
                b[y][x] += 1
        if b[y][x] >= 2:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Memory Limit Exceeded

Solution code:
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w=map(int,raw_input().split())
g=[map(int,raw_input().split()) for _ in xrange(h)]
pos=[[] for _ in xrange(h*w)]
for i in xrange(h):
    for j in xrange(w):
        pos[g[i][j]-1]=[i,j]

dy=(1,0,-1,0)
dx=(0,1,0,-1)
stop=[[[] for _ in xrange(w)] for _ in xrange(h)]
ans=0
for i in xrange(h*w):
    y,x=pos[i]
    for j in xrange(4):
        ny=y+dy[j];nx=x+dx[j]
        if check(ny,nx):
            if g[ny][nx]<g[y][x]:
                for k in stop[ny][nx]:
                    stop[y][x].append(k)
    cnt=len(set(stop[y][x]))
    if cnt>=2:
        ans+=1
    elif cnt==0:
        stop[y][x].append(g[y][x])

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w=map(int,raw_input().split())
g=[map(int,raw_input().split()) for _ in xrange(h)]
pos=[-1]*(h*w)
for i in xrange(h):
    for j in xrange(w):
        pos[g[i][j]-1]=[i,j]

dy=(1,0,-1,0)
dx=(0,1,0,-1)
stop=[[] for _ in xrange(h*w)]
ans=0
for i in xrange(h*w):
    y,x=pos[i]
    for j in xrange(4):
        ny=y+dy[j];nx=x+dx[j]
        if check(ny,nx):
            if g[ny][nx]<g[y][x]:
                for k in stop[g[ny][nx]-1]:
                    stop[i].append(k)
    cnt=len(set(stop[i]))
    if cnt>=2:
        ans+=1
    elif cnt==0:
        stop[i].append(g[y][x])

print(ans)

Submission status: Accepted

Solution code:
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w=map(int,raw_input().split())
g=[map(int,raw_input().split()) for _ in xrange(h)]
pos=[-1]*(h*w)
for i in xrange(h):
    for j in xrange(w):
        pos[g[i][j]-1]=[i,j]

dy=(1,0,-1,0)
dx=(0,1,0,-1)
stop=[set() for _ in xrange(h*w)]
ans=0
for i in xrange(h*w):
    y,x=pos[i]
    for j in xrange(4):
        ny=y+dy[j];nx=x+dx[j]
        if check(ny,nx):
            if g[ny][nx]<g[y][x]:
                for k in list(stop[g[ny][nx]-1]):
                    stop[i].add(k)
    cnt=len(stop[i])
    if cnt>=2:
        ans+=1
    elif cnt==0:
        stop[i].add(g[y][x])

print(ans)

Submission status: Accepted

Solution code:
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w=map(int,raw_input().split())
g=[map(int,raw_input().split()) for _ in xrange(h)]
pos=[-1]*(h*w)
for i in xrange(h):
    for j in xrange(w):
        pos[g[i][j]-1]=[i,j]

dy=(1,0,-1,0)
dx=(0,1,0,-1)
stop=[set() for _ in xrange(h*w)]
ans=0
for i in xrange(h*w):
    y,x=pos[i]
    for j in xrange(4):
        ny=y+dy[j];nx=x+dx[j]
        if check(ny,nx):
            if g[ny][nx]<g[y][x]:
                stop[i]=stop[i]|stop[g[ny][nx]-1]
    cnt=len(stop[i])
    if cnt>=2:
        ans+=1
    elif cnt==0:
        stop[i].add(g[y][x])

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = [None]*(H*W)
S = [list(map(int, input().split())) for i in range(H)]
G = [[None]*W for i in range(H)]
for i in range(H):
    s = S[i]
    for j in range(W):
        M[s[j]-1] = (i, j)
D = 0,-1,0,1,0

ans = 0
for i in range(H*W):
    y, x = M[i]
    g = None
    for k in range(4):
        nx = x + D[k]; ny = y + D[k+1]
        if not 0 <= nx < W or not 0 <= ny < H or i+1 < S[ny][nx]:
            continue
        if g is None:
            g = G[ny][nx]
        elif g != G[ny][nx]:
            g = -1
    if g == -1:
        ans += 1
    if g is None:
        G[y][x] = i
    else:
        G[y][x] = g
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

tmp_list = [list(map(int, input().split())) for i in range(H)]
ans_list = [[None for i in range(W)] for j in range(H)]



# j: 横方向(0 ~ W-1)
# i: 縦方向(0 ~ H-1)
def search_func(i, j):
    
    if not (not ans_list[i][j]):
        return ans_list[i][j]
    
    # print("i =", i, ",j =", j)
    # ４方向に探索する。
    add_list = set()
    if j != 0 and tmp_list[i][j] > tmp_list[i][j-1]:
        add_list = add_list.union(search_func(i, j-1))
    if j != (W-1) and tmp_list[i][j] > tmp_list[i][j+1]:
        add_list = add_list.union(search_func(i, j+1))
    if i != 0 and tmp_list[i][j] > tmp_list[i-1][j]:
        add_list = add_list.union(search_func(i-1, j))
    if i != (H-1) and tmp_list[i][j] > tmp_list[i+1][j]:
        add_list = add_list.union(search_func(i+1, j))
        
    # ４方向は囲まれていた
    if not add_list:
        ans_list[i][j] = set({tmp_list[i][j]})
    else:
        ans_list[i][j] = add_list
    return ans_list[i][j]
    

sort_list = []
for i in range(H):
    for j in range(W):
        sort_list.append([tmp_list[i][j], i, j])

# キーにしたがってソートする。
sort2_list = sorted(sort_list, key=lambda x: x[0])

final_ans = 0
for item in sort2_list:
    if len(search_func(item[1], item[2])) > 1:
        final_ans += 1
print(final_ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
  INF = 10 ** 7
  h, w = map(int, input().split())
  mp = [[INF] + list(map(int, input().split())) + [INF] for _ in range(h)]
  mp.insert(0, [INF] * (w + 2))
  mp.append([INF] * (w + 2))
  ridge = [[None] * (w + 2) for _ in range(h + 2)]
  vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
  
  def is_ridge(x, y):
    to_set = set()
    for dx, dy in vec:
      nx, ny = x + dx, y + dy
      temp = ridge[ny][nx]
      if temp != None:
        if temp is True:
          ridge[y][x] = True
          return True
        else:
          to_set.add(temp)
    
    if not to_set:
      ridge[y][x] = (x, y)
    elif len(to_set) == 1:
      ridge[y][x] = list(to_set)[0]
    else:
      ridge[y][x] = True
    return ridge[y][x]
  
  que = []
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      h = mp[y][x]
      heappush(que, (h, x, y))
  
  ans = 0
  while que:
    _, x, y = heappop(que)
    if is_ridge(x, y) is True:
      ans += 1
  print(ans)

main()