小黑代码1

class Solution:def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:# 一定无解的情况if grid[0][0] == 1 or grid[-1][-1] == 1:return -1# 矩阵长度n = len(grid)# 起点即终点if n == 1:return 1# 访问集合seen = {(0, 0)}# 初始化队列q = collections.deque([[(0,0), 1]])# 开始进行队列操作while q:# 出队top = q.popleft()pos = top[0]dis = top[1]# 八个方向尝试for di in [[1, 0], [0, 1], [1, 1], [-1, 0], [0, -1], [-1, -1], [1, -1], [-1, 1]]:# 构造坐标pos_x = pos[0] + di[0]pos_y = pos[1] + di[1]# 判断是否出界以及有障碍物if 0 <= pos_x < n and 0 <= pos_y < n and (pos_x, pos_y) not in seen and not grid[pos_x][pos_y]:# 到达终点if pos_x == pos_y == n - 1:return dis + 1q.append(((pos_x, pos_y), dis + 1))seen.add((pos_x, pos_y))return -1            

小黑代码2

# A*算法类
class Astar(object):def __init__(self, status, target, g):self.status = statusself.target = targetself.g = gself.h = Astar.getH(status, target)self.f = self.g + self.h@staticmethoddef getH(status, target):print(status)dis_x = abs(status[0]-target[0])dis_y = abs(status[1]-target[1])return max(dis_x, dis_y)# 排序函数def __lt__(self, other):if self.f == other.f:return self.g < other.greturn self.f < other.f
class Solution:def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:# 一定无解的情况if grid[0][0] == 1 or grid[-1][-1] == 1:return -1# 数组长度n = len(grid)# 起点即是终点的情况if n == 1:return 1# 初始化优先队列q = [Astar((0, 0), (n-1, n-1), 1)]# 访问数组visited = set()# 开始进行A*算法迭代while q:# “假设距离”最近的出队top = heapq.heappop(q)status = top.statusg = top.gif status in visited:continuevisited.add(status)# 8个方向for di in [(-1,-1), (1,0), (0,1), (-1,0), (0,-1), (1,1), (1,-1), (-1,1)]:# 构造心得坐标new_pos = [0, 0]new_pos[0] = status[0] + di[0]new_pos[1] = status[1] + di[1]new_pos = (new_pos[0], new_pos[1])# 准入条件：未出界+无障碍+没走过if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n and not grid[new_pos[0]][new_pos[1]]:# 是否到终点if new_pos[0] ==new_pos[1] == n - 1:return g + 1# 入队列heapq.heappush(q, Astar(new_pos, (n-1, n-1), g + 1))return -1

小黑生活

晚饭吉野家宫保鸡丁套餐

琴房又没开门又没练成琴，难受，来个烤冷面

来一小时按摩

回家一瓶勇闯天涯+牛排

早上公司楼底下太平洋咖啡，顺便笔试，然后飞速去实习

午饭吉野家牛肉饭

期待晚上跟尚香的疯狂星期四

公司里来了只猫咪，好可爱呀

抢到了同仁医院的号

半马领物单出来了

晚饭麦当劳牛堡

回去找尚香的疯狂星期四+DQ冰激凌+骑车吹风，生活要有仪式感

早餐宇飞牛肉面啦

上午笔试，感觉好难啊，之后喝杯喜茶

下午和动哥去按摩+足疗，喝杯DQ

花500+买的便携屏幕到了，虽然质量不符合预期，但是也还能用，以后咖啡厅学习可以边看课边敲代码啦

晚上两个半小时的笔试

算法题一直出bug了，小黑去潘家园图书馆调试

打印比赛承诺书，跟尚香奥林匹克公园约学习啦

到达弥远咖啡，继续调试bug

晚饭肯德基全鸡+牛堡

北京难得的蓝色啦，走在奥体景观大道上真舒服，去领物资

去附近骑个车，喝杯茶百道

早餐牛排，出发半程马拉松

鸣枪起跑啦，这个天气跑得相当舒服

回去的地铁上人好多啊

回家后报名了一个多月后的密云马拉松，跑起来～

又增添了一块奖牌

照片也传过来了

下午喜茶海盐咖啡，继续想那个A*代码的bug，总算想出来啦

晚上和老黑们去吃串串香啦，祝贺阿黄公务员上岸

中老黑吃吐了

回去修个脚，完美，发博客，晚安！！