设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › Python交流 › Python：每日一题 327
12
返回列表 发新帖
楼主: zltzlt

[已解决]Python：每日一题 327

[复制链接]
William4869
发表于 2020-2-8 22:18:10 | 显示全部楼层
zltzlt 发表于 2020-2-8 22:03
解答错误

输入：

到不了输出-1？

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

TJBEST
发表于 2020-2-8 22:22:32 | 显示全部楼层
zltzlt 发表于 2020-2-8 22:09
确实会超时哦

还有我超时的例子能否明示？我查了一下，我这个算法是ip路由的一种算法，这个算法不应该太慢
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

William4869
发表于 2020-2-8 22:23:19 | 显示全部楼层
zltzlt 发表于 2020-2-8 22:03
解答错误

输入：

改了
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

Croper
发表于 2020-2-8 22:42:17 | 显示全部楼层
zltzlt 发表于 2020-2-8 22:01
输入：
输出：23
预期结果：21


还是不熟。。改了下估计路径的函数
  1. class SortedList(list):
  2.     def __init__(self,key=lambda x:x):
  3.         super().__init__();
  4.         self.key=key
  5.         self.reversed=reversed
  6.         
  7.     def append(self,ele):
  8.         p,q=0,len(self)
  9.         while p<q:
  10.             n=(p+q)//2
  11.             if self.key(ele)>self.key(self[n]):
  12.                 q=n
  13.             else:
  14.                 p=n+1
  15.         super().insert(p,ele)

  17. def func327(map):
  18.     if len(map)==0 or len(map[0])==0:
  19.         return -1;
  20.     start_pos=target_pos=None;
  21.     for i in range(len(map)):
  22.         for j in range(len(map[i])):
  23.             if map[i][j]=='S':
  24.                 map[i][j]=0
  25.                 start_pos=(i,j)
  26.             if map[i][j]=='T':
  27.                 target_pos=(i,j)


  30.     def valid(pos:tuple):
  31.         return 0<=pos[0]<len(map) and 0<=pos[1]<len(map[pos[0]])

  33.     offset=((1,0),(-1,0),(0,1),(0,-1))
  34.     inner=[]

  36.     minx=maxx=start_pos[1]
  37.     miny=maxy=start_pos[0]

  39.     def MinRemainLength(t:tuple):
  40.         y,x=t
  41.         y0,x0=start_pos
  42.         y1,x1=target_pos
  43.         deltax,deltay=abs(x-x1),abs(y-y1)
  44.         if (abs(y-y1)>abs(y0-y1)):
  45.             deltax=min(abs(minx-1-x)+abs(minx-1-x1),abs(maxx+1-x)+abs(maxx+1-x1))
  46.         if (abs(x-x1)>abs(x0-x1)):
  47.             deltay=min(abs(miny-1-y)+abs(miny-1-y1),abs(maxy+1-y)+abs(maxy+1-y1))
  48.         return (deltax+deltay+map[y][x])*10000+map[y][x]

  50.     outer=SortedList(key=MinRemainLength)

  52.     outer.append(start_pos)

  54.     while len(outer)>0:
  55.         #printl2(map,MinRemainLength)
  56.         #print()
  57.         #for i in outer:
  58.             #print(map[i[0]][i[1]],end=" ")
  59.         #print()
  60.         #z=input()
  61.         pos=outer.pop()
  62.         inner.append(pos)
  63.         minx=min(minx,pos[1])
  64.         maxx=max(maxx,pos[1])
  65.         miny=min(miny,pos[0])
  66.         maxy=max(maxy,pos[0])
  67.         n=map[pos[0]][pos[1]]

  69.         for i in range(4):
  70.             y,x=pos[0]+offset[i][0],pos[1]+offset[i][1]
  71.             if valid((y,x)):
  72.                 if (y,x) in inner:
  73.                     continue
  74.                 c=map[y][x]
  75.                 if c=='T':
  76.                     return n+1
  77.                 if c=='.':
  78.                     map[y][x]=n+1
  79.                     outer.append((y,x))
  80.                
  81.     return -1
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

阴阳神万物主
发表于 2020-2-8 23:36:28 | 显示全部楼层
我暂时不去考虑超时的问题
  1. def solve(t_map)->int:
  2.     s = []
  3.     x,y = len(t_map),len(t_map[0])
  4.     for l in range(x):
  5.         if 'S' in t_map[l]:
  6.             s = (l,t_map[l].index('S'))
  7.         elif s:
  8.             break
  9.     d = ((-1,0),(1,0),(0,-1),(0,1))
  10.     log = []
  11.     def move(pos,n=0):
  12.         if t_map[pos[0]][pos[1]] == 'T':
  13.             return n
  14.         log.append(pos)
  15.         memory = []
  16.         for de in d:
  17.             np = (pos[0]+de[0],pos[1]+de[1])
  18.             if (0<=np[0]<x and 0<=np[1]<y) and (np not in log) and t_map[np[0]][np[1]] != '#':
  19.                 memory.append(move(np,n+1))
  20.         log.pop()
  21.         return min(memory) if memory else int('f'*10,base=16)
  22.     res = move(s)
  23.     return -1 if res == int('f'*10,base=16) else res
  24. if __name__ == '__main__':
  25.     print('示例1 2 输出：',solve([
  26.   ['S', '.'],
  27.   ['#', 'T']
  28. ]))
  29.     print('别人错的 11# 2 输出：',solve([
  30.         ['.', 'T', '.', 'S', '.', '#', '.', '.', '.', '.'],
  31.         ['#', '.', '.', '.', '.', '#', '.', '#', '.', '.'],
  32.         ['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
  33.         ['.', '.', '.', '.', '#', '#', '.', '.', '.', '.'],
  34.         ['#', '#', '.', '.', '.', '.', '.', '#', '.', '#']]))
  35.     print('别人错的 13# 21 输出：',solve([
  36.         ['.', '#', '.', '.', '#', '.', '.', '.', '.', '#', '.', '#'],
  37.         ['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.'],
  38.         ['.', '.', '.', '.', '#', '#', '#', '#', '#', 'S', '.', '.'],
  39.         ['#', '#', '.', '#', '.', '#', '.', '.', '#', '#', '.', '.'],
  40.         ['.', '#', '.', '.', '.', '#', '#', '#', '.', '#', '#', '.'],
  41.         ['.', '.', '#', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
  42.         ['.', '.', '#', '.', '#', '#', '#', '.', '.', '.', '.', '.'],
  43.         ['.', '#', '.', '#', '#', '#', '.', '#', '.', '#', '.', '.'],
  44.         ['#', '.', '.', '.', '#', '.', '.', '#', '.', '#', '#', '.'],
  45.         ['.', '.', '#', '#', '#', '.', '#', '#', '.', '.', '.', '.'],
  46.         ['#', '.', '#', '#', '.', '.', '#', '#', '#', '.', '#', '.'],
  47.         ['.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#', '.'],
  48.         ['#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '#'],
  49.         ['#', '.', '#', '#', '#', 'T', '.', '#', '#', '.', '.', '#'],
  50.         ['.', '#', '#', '#', '.', '#', '.', '.', '.', '#', '.', '.'],
  51.         ['#', '.', '.', '.', '.', '#', '.', '#', '#', '.', '.', '.']]))
  52.     print('别人错的 14# -1 输出：',solve([
  53.         ['.', '#', '.', '#', '#', '.'],
  54.         ['.', '#', 'S', '.', '#', '.'],
  55.         ['.', '#', '.', '#', '#', '#'],
  56.         ['.', '.', '#', '.', '#', '.'],
  57.         ['.', '.', '.', '.', '.', '.'],
  58.         ['.', '#', 'T', '.', '.', '.']]))
复制代码

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
zltzlt + 2 + 2

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-9 15:37:15 | 显示全部楼层
William4869 发表于 2020-2-8 21:50
BFS搜索，，，应该没什么问题

554 ms
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-9 15:38:11 | 显示全部楼层
TJBEST 发表于 2020-2-8 22:22
还有我超时的例子能否明示？我查了一下，我这个算法是ip路由的一种算法，这个算法不应该太慢

你确定要贴出来吗？
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-9 15:49:45 | 显示全部楼层
TJBEST 发表于 2020-2-8 22:22
还有我超时的例子能否明示？我查了一下，我这个算法是ip路由的一种算法，这个算法不应该太慢

testdata.zip (34.42 KB, 下载次数: 8)
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

蒋博文
发表于 2020-2-9 16:54:25 | 显示全部楼层
本帖最后由 zltzlt 于 2020-2-9 21:25 编辑
  1. class Node(object):
  2.     def __init__(self, x, y):
  3.         self.x = x
  4.         self.y = y
  5.         self.next = None


  8. class TraceRecode(object):
  9.     def __init__(self):
  10.         self.first = None
  11.         self.last = None

  13.     def insert(self, x, y):
  14.         newNode = Node(x, y)
  15.         if self.first == None:
  16.             self.first = newNode
  17.             self.last = newNode
  18.         else:
  19.             self.last.next = newNode
  20.             self.last = newNode

  22.     def delete(self):
  23.         if self.first == None:
  24.             print('队列已经空了')
  25.             return
  26.         newNode = self.first
  27.         while newNode.next != self.last:
  28.             newNode = newNode.next
  29.         newNode.next = self.last.next  # 删除栈顶元素
  30.         self.last = newNode


  33. def chkExit(MAZE, x, y, ex, ey):
  34.     '''
  35.     判断是否为出口，
  36.     条件：上下左右肯定存在一个走过的路（坐标）
  37.     '''
  38.     if x == ex and y == ey:
  39.         if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 2):
  40.             return 1
  41.         if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 2 or MAZE[x][y + 1] == 1):
  42.             return 1
  43.         if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 2 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 1):
  44.             return 1
  45.         if (MAZE[x - 1][y] == 2 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 1):
  46.             return 1
  47.     return 0


  50. if __name__ == '__main__':
  51.     Exitx,Exity = 8,10
  52.     # 迷宫，0表示路，1表示墙
  53.     MAZE = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  54.             [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
  55.             [1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1],
  56.             [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
  57.             [1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1],
  58.             [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
  59.             [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1],
  60.             [1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1],
  61.             [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
  62.             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ]
  63.     path = TraceRecode()
  64.     x, y = 1, 1  # 初始路径
  65.     print('迷宫的路径（0标记的部分）')
  66.     for i in range(10):
  67.         for j in range(12):
  68.             print(MAZE[i][j], end='')
  69.         print()

  71.     while x <= Exitx and y <= Exity:
  72.         MAZE[x][y] = 2  # 走过的路径标注为2
  73.         '''
  74.         判断当前位置的上下左右是否可以移动，如果可以移动，将该位置入栈，若无路可走，则回退到上一个位置，重新检查
  75.         '''
  76.         if MAZE[x - 1][y] == 0:
  77.             # 向上走
  78.             x -= 1
  79.             path.insert(x, y)
  80.         elif MAZE[x][y + 1] == 0:
  81.             # 向右走
  82.             y += 1
  83.             path.insert(x, y)
  84.         elif MAZE[x + 1][y] == 0:
  85.             # 向下走
  86.             x += 1
  87.             path.insert(x, y)
  88.         elif MAZE[x][y - 1] == 0:
  89.             # 向左走
  90.             y -= 1
  91.             path.insert(x, y)
  92.         # 检查是否为出口
  93.         elif chkExit(MAZE, x, y, Exitx, Exity) == 1:
  94.             break
  95.         else:
  96.             # 如果上下左右都不通了，也不是出口，就回退到拐点
  97.             MAZE[x][y] = 2
  98.             path.delete()  # 删除栈顶元素，获得上次添加的坐标
  99.             x = path.last.x
  100.             y = path.last.y
  101.     print('走过的路径（2标记的部分）')
  102.     for i in range(10):
  103.         for j in range(12):
  104.             print(MAZE[i][j], end='')
  105.         print()
复制代码

不知道对不对，试试吧。

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

阴阳神万物主
发表于 2020-2-10 01:45:28 | 显示全部楼层
结贴之前居然没有测我的？！伤心.jpg
https://fishc.com.cn/forum.php?m ... 642&pid=4334817
我明明没有修炼醉明星居士家的功法，为啥存在感还是这么低？！
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

fan1993423
发表于 2020-2-10 17:58:06 | 显示全部楼层
本帖最后由 fan1993423 于 2020-2-10 21:13 编辑
  1. def fun327(lst):
  2.     height,width=len(lst),len(lst[0])
  3.     S_coor,T_coor=[],[]
  4.     new_map=[[0 for _ in range(width)] for _ in range(height)]
  5.     for i in range(height):
  6.         for j in range(width):
  7.             if lst[i][j]=='S':
  8.                 S_coor+=[[i,j]]
  9.             elif lst[i][j]=='T':
  10.                 T_coor+=[i,j]
  11.     move_x,move_y=[1,0,-1,0],[0,1,0,-1]
  12.     while S_coor:
  13.         a=S_coor.pop(0)
  14.         if a==T_coor:
  15.             break
  16.         p,q=a[0],a[1]
  17.         for i in range(4):
  18.             new_x,new_y=p+move_x[i],q+move_y[i]
  19.             if 0<=new_x<height and 0<=new_y<width and lst[new_x][new_y]!='#' and (new_map[new_x][new_y]==0 or new_map[new_x][new_y]>new_map[p][q]) and lst[new_x][new_y]!='S':
  20.                 new_map[new_x][new_y]=new_map[p][q]+1
  21.                 S_coor.append([new_x,new_y])
  22.     return new_map[T_coor[0]][T_coor[1]] if new_map[T_coor[0]][T_coor[1]] else -1
复制代码

康康来测一下我这个对不对

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
zltzlt + 2 + 2

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-10 18:00:18 | 显示全部楼层
Croper 发表于 2020-2-8 22:42
还是不熟。。改了下估计路径的函数

652 ms
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-10 18:01:32 | 显示全部楼层
阴阳神万物主 发表于 2020-2-8 23:36
我暂时不去考虑超时的问题

输入 [['.', '.', '#', '#', '.', '#', '#', '.', '#', '#'], ['#', '.', '.', '#', '.', '.', '.', '#', '#', '#'], ['.', '.', '.', '.', '.', '.', '.', '#', '#', '#'], ['.', '#', '#', '.', '#', '.', '.', '.', '.', '#'], ['.', '.', '#', '#', '.', '.', '#', '#', '#', '.'], ['.', '.', '#', '.', '.', '#', '.', '.', '.', '.'], ['.', '.', '#', '.', '.', '.', '#', '.', '.', '.'], ['#', '.', '.', '.', '.', '#', '.', '.', '.', '#'], ['.', '.', '.', 'S', 'T', '.', '.', '#', '.', '.'], ['.', '.', '.', '#', '.', '#', '.', '#', '#', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.']] 超时
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-10 18:01:59 | 显示全部楼层
阴阳神万物主 发表于 2020-2-10 01:45
结贴之前居然没有测我的？！伤心.jpg
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=1 ...

漏了
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-10 18:02:48 | 显示全部楼层
fan1993423 发表于 2020-2-10 17:58
康康来测一下我这个对不对

解答错误

输入：
  1. [['.', '#', '.', '#', '#', '.'], ['.', '#', 'S', '.', '#', '.'], ['.', '#', '.', '#', '#', '#'], ['.', '.', '#', '.', '#', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '#', 'T', '.', '.', '.']]
复制代码

输出：0
预期结果：-1
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

fan1993423
发表于 2020-2-10 21:12:37 | 显示全部楼层
zltzlt 发表于 2020-2-10 18:02
解答错误

输入：


忘了写成-1了，0就是走不通的意思，已改

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
zltzlt + 2 + 2

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zltzlt
 楼主| 发表于 2020-2-11 19:04:37 | 显示全部楼层
fan1993423 发表于 2020-2-10 17:58
康康来测一下我这个对不对

现在没有错误，但是会超时
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

12
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-12 13:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表