結果
問題 | No.2928 Gridpath |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:21:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 1,572 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 78,508 KB |
最終ジャッジ日時 | 2024-10-12 16:21:44 |
合計ジャッジ時間 | 2,559 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
from collections import defaultdict, deque, Counter # from functools import cache # import copy from itertools import combinations, permutations, product, accumulate, groupby, chain # from more_itertools import distinct_permutations from heapq import heapify, heappop, heappush import math import bisect # from pprint import pprint from random import randint, shuffle, randrange # from sortedcontainers import SortedSet, SortedList, SortedDict import sys # sys.setrecursionlimit(2000000) input = lambda: sys.stdin.readline().rstrip('\n') inf = float('inf') mod1 = 10**9+7 mod2 = 998244353 def ceil_div(x, y): return -(-x//y) ################################################# def ok(ni, nj, i, j): if not (0 <= ni < H and 0 <= nj < W) or been[ni][nj]: return False for di, dj in D: if not (0 <= ni+di < H and 0 <= nj+dj < W): continue if ni+di == i and nj+dj == j: continue if been[ni+di][nj+dj]: return False return True H, W = map(int, input().split()) si, sj = map(lambda x: int(x)-1, input().split()) ti, tj = map(lambda x: int(x)-1, input().split()) D = [(0, 1), (0, -1), (1, 0), (-1, 0)] been = [[False]*W for _ in range(H)] stack = [(si, sj)] ans = 0 while stack: i, j = stack.pop() if i >= 0: if i == ti and j == tj: ans += 1 continue been[i][j] = True stack.append((~i, j)) for di, dj in D: ni, nj = i+di, j+dj if ok(ni, nj, i, j): stack.append((ni, nj)) else: i = ~i been[i][j] = False print(ans)