格式化时间

365 Or 366？

一马当先

def valid(Node,move):     horse=Node.sit     mid=(horse[0]+move[0],horse[1]+move[1]) if (mid[0]&gt;=0)&amp;(mid[1]&gt;=0)&amp;(mid[0]&lt;=m)&amp;(mid[1]&lt;=n): return True else: return False class node: def __init__(self,sit,father): self.sit=sit self.father=father def set_father(self,Node): self.father=Node def get(self): return self.sit def move_Node(Node,i): return node((Node.sit[0]+i[0],Node.sit[1]+i[1]),None) def H_cost(Node):     cost=abs(Node.get()[0]-m)+abs(Node.get()[1]-n) return cost if __name__ == &#x27;__main__&#x27;:     move = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]     horse=node((0,0),None)     goal=(m,n)     closeList=[]     openList=[]     costList=[]     openList.append(horse)     costList.append(H_cost(horse))     count=-1 while len(openList)&gt;0: id=costList.index(min(costList))         horse=openList[id] del openList[id] del costList[id]         closeList.append(horse.get()) if horse.get()==goal:             count=0 break for i in move: if valid(horse,i):                 temp=move_Node(horse,i) if closeList.count(temp.get())==0:                     temp.set_father(horse)                     openList.append(temp)                     costList.append(H_cost(temp)) while (horse.father!=None)&amp;(count&gt;-1):         horse=horse.father         count+=1 print(count)

由于我的BFS跟我说超时了，我就重新用贪婪优先算法写了一个

贪婪优先算法

#题目：一马当先&#x27;&#x27;&#x27;下过象棋的人都知道，马只能走&#x27;日&#x27;字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1. 如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。&#x27;&#x27;&#x27;from copy import deepcopyn=int(input(&quot;行数：&quot;))m=int(input(&quot;列数:&quot;))d = [[1, 2], [2, 1], [-1, -2], [-2, -1], [1, -2], [-1, 2], [2, -1], [-2, 1]]a=[[0,0]]count=0def crail(a,d,n,m): b=[] for i,j in a: for s_1,s_2 in d: count=+1 p=i+s_1 q=j+s_2 if p==n and q==m: b.append([p,q]) t=False break else: b.append([p,q]) return bdef duduce(f,a): for x in f: if x[0]&lt;0 or x[1]&lt;0: a.remove(x) return aif n==1: if m%4==2: print(m/2) else: print(-1)elif m==1: if n%4==2: print(n/2) else: print(-1)else: t=True while t: f=crail(a,d,n,m) count=count+1 a=deepcopy(f) a=duduce(f,a) for y in a: if y[0]==n and y[1]==m: print(count) t=False break elif count&gt;5: print(-1) t=False break

暴力解法

数学上可以用归纳法证明m&gt;1,n&gt;1时一定可以跳到右上角n=1 m%4=2时也可以，其他情况不行关键在于找出最短步数<pre><code>if n&gt;m: n,m=m,n if n==1 and m%4 !=2: print(-1) #其它情况一定可以跳到右上角 else: k=1 alist={(0,0)} blist=[] aset={(0,0)} while (m,n) not in aset: for (x,y) in alist: if x+1 in range(m+1) and y+2 in range(n+1) and(x+1,y+2) not in aset: blist.append((x+1,y+2)) if x+1 in range(m+1) and y-2 in range(n+1) and(x+1,y-2) not in aset: blist.append((x+1,y-2)) if x-1 in range(m+1) and y+2 in range(n+1) and(x-1,y+2) not in aset: blist.append((x-1,y+2)) if x-1 in range(m+1) and y-2 in range(n+1) and(x-1,y-2) not in aset: blist.append((x-1,y-2)) if x-2 in range(m+1) and y-1 in range(n+1) and(x-2,y-1) not in aset: blist.append((x-2,y-1)) if x-2 in range(m+1) and y+1 in range(n+1) and(x-2,y+1) not in aset: blist.append((x-2,y+1)) if x+2 in range(m+1) and y-1 in range(n+1) and(x+2,y-1) not in aset: blist.append((x+2,y-1)) if x+2 in range(m+1) and y+1 in range(n+1) and(x+2,y-1) not in aset: blist.append((x+2,y+1)) if (m,n) in blist: print(k) aset=aset.union(blist) alist=blist blist=[] k=k+1</code></pre>

没学过算法的人的解答

a=(2*n-m)/3;b=(2*m-n)/3 print(4 if (n==2 and m==2) else (int(a+b) if a&gt;=0 and b&gt;=0 and a//1==a and b//1==b else -1 ))

不懂算法 但是可以解二元一次方程 要注意m=n=2时有特解，需要单独判断 

强行2行搞定

&quot;&quot;&quot;下过象棋的人都知道，马只能走&#x27;日&#x27;字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1. 如n=1，m=2, 则至少需要1步；若n=1，m=3,则输出-1。&quot;&quot;&quot; # 深度优先搜索 def dfs(area): def dfs_0(coordinate, step): nonlocal step_min, area, record_points, ans_ways # 判断边界 if coordinate in record_points: record_points.append(coordinate) return else: record_points.append(coordinate) if coordinate[0] &gt; area[0] or coordinate[0] &lt; 0 or coordinate[1] &lt; 0 or coordinate[1] &gt; area[1]: return if coordinate[0] == area[0] and coordinate[1] == area[1]: ans_ways.append(record_points.copy()) if step_min &gt; step: step_min = step return if step &gt; step_min: return # 移动到下一个点位 move = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)) for i in move: next_coordinate = (coordinate[0] + i[0], coordinate[1] + i[1]) dfs_0(next_coordinate, step + 1) record_points.pop() return coordinate = (0, 0) step_min = 9999 record_points = [] ans_ways = [] dfs_0(coordinate, 0) ans_ways = [i for i in ans_ways if len(i) &lt;= step_min + 1] return [step_min, len(ans_ways), ans_ways] # 广度优先搜索 class PathPoint(object): def __init__(self, layer, f_index, coordinate): self.layer = layer self.f_index = f_index self.coordinate = coordinate def bfs(area): record_points = [] success_points = [] ans_ways = [] record_set = set() move = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)) i = 0 success_layer = 999 record_points.append(PathPoint(0, None, (0, 0))) while i &lt; len(record_points) and record_points[i].layer &lt; success_layer: for mov in move: new_coordinate = (record_points[i].coordinate[0] + mov[0], record_points[i].coordinate[1] + mov[1]) if new_coordinate[0] &gt; area[0] or new_coordinate[0] &lt; 0 or new_coordinate[1] &lt; 0 or new_coordinate[1] &gt; \ area[1]: continue if new_coordinate in record_set: continue record_set.add(new_coordinate) record_points.append(PathPoint(record_points[i].layer + 1, i, new_coordinate)) if new_coordinate[0] == area[0] and new_coordinate[1] == area[1]: success_points.append(len(record_points) - 1) success_layer = record_points[i].layer + 1 i += 1 point = 0 for j in success_points: ans_ways.append([]) ans_ways[point].append(record_points[j].coordinate) k = record_points[j].f_index while not record_points[k].f_index is None: ans_ways[point].append(record_points[k].coordinate) k = record_points[k].f_index point += 1 [ls.sort() for ls in ans_ways] return [success_layer, len(ans_ways), ans_ways] if __name__ == &quot;__main__&quot;: # step_min, num, ans_ways = dfs((7, 7)) # print(step_min) # print(num) # [print(i) for i in ans_ways if len(i)] n = 1 m = 2 step_min, num, ans_ways = bfs((n, m)) if step_min == 999: print(-1) else: print(step_min) # print(step_min) # print(num) # [print(i) for i in ans_ways if len(i)]

DFS and BFS

if n &gt; m: n, m = m, nif n == 1 and m % 4 != 2: print(-1)elif n == m == 2: print(4)elif n==1 and m==2: print(1)else: print(n+m)

这个虽然可以过，但是大戳特错

算法不懂

# 列出x和y方向所有可能的走法 dx = [1, 2, 2, 1, -1, -2, -2, -1] dy = [-2, -1, 1, 2, 2, 1, -1, -2] # 创建一个嵌套的列表,用来存储整个棋盘所有的点 # 类似于数组 # 列表表达式快速生成的,也可以用常规方法生成 # 这里注意一下:4*5的棋盘,代表有5*6个点 vis = [([0] * (m + 1)) for i in range(n + 1)] # 创建一个列表,用来存储基于当前点位,所有等待访问的点的横坐标和纵坐标,以及本次走过的步长 # 因为有三个数据,所以列表里面嵌套一个元组 # 初始化都为0,代表从坐标轴原点开始走 q = [(0, 0, 0)] # 标记为1,代表这个点我们走过了,这里代表从原点开始走了 vis[0][0] = 1 # 循环执行的条件是:在当前点位,只要有未访问的点就执行这个循环 while q: # 抛出 q里面的第一个元组数据,赋值给temp temp = q.pop(0) # 判断是否到达终点,如果到达终点,则直接输出步长,代表走了多少步 if temp[0] == n and temp[1] == m: print(temp[2]) break # zip()函数:把两个列表变成一个列表+元组的形式 # 遍历所有的走法 for x,y in zip(dx,dy): # 这里,curx和cury分别代表了即将要走的点 # 通过for循环,能把当前位置所有能走的点都遍历到 curx = temp[0] + x cury = temp[1] + y # curstep放在这里,只有成功走了一个点,这个变量的值才会增加1 curstep = temp[2] + 1 # 判断是否超出边界,或者已经走过 if 0 &lt;= curx &lt;= n and 0 &lt;= cury &lt;= m and vis[curx][cury] != 1: # 未超出边界,或者未走过这个点,则标记为1,代表这个点走了 vis[curx][cury] = 1 # 把这个点和步长加入到q中,提供给下一次while循环使用,下一次循环就会从这个点开始往下走 q.append((curx,cury,curstep)) else: print(-1)

BFS-广度优先算法

我都看不懂你们在干嘛？？整理明白后，忘了2,2特例一直没通过。。。if n &gt; m:     n, m = m, n if n == 1 and m % 4 != 2: print(-1) elif n == m == 2: print(4) else: print((n+m) // 3 + abs(n+m) % 3)

我不明白你这个怎么通过的。。。。漏洞百出

你的我试了可以通过，但是，我觉得除以3是有问题的，3*3 是两步，但3*198只有67步说不通的，至少198/2   99步左右的， 一步最多走步长2, 你这走的不是日，是口口口了

你这个如果是2，7结果就不对吧

那结尾是不是可以直接改成print((m+n)//2)

其实把网格铺成直线看就是n+m的一条线，马每次能走的步数就是2+1,2-1,1-2，-1-3这几种，当然不可能倒退了。。。

纯数学方法

direction = ([1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2,-1], [-2, 1], [-2, -1]) routine = [(0, 0)] #统计走过的格子 count = 0 temp_x, temp_y = 0, 0 while routine: now_x, now_y = routine.pop() if (now_x, now_y) == (m, n): break for x, y in direction: if (x, y) != (-temp_x, -temp_y): now_x += x now_y += y count += 1 if now_x &lt; 0 or now_x &gt; m or now_y &lt; 0 or now_y &gt; n: count -= 1 now_x -= x now_y -= y continue else: temp_x, temp_y = x, y routine.append((now_x, now_y)) break if (now_x, now_y) != (m, n): count = 0 if count != 0: print(count) else: print(-1)

你这就一个注释生怕我们看得懂呢

你好,请问怎么保证存在可以到达m点的情况时,第一条路线是最短的路线呢


广度搜索2

direction = ([1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2,-1], [-2, 1], [-2, -1]) routine = [(0, 0)] #统计走过的格子 count = 0 temp_x, temp_y = 0, 0 while routine:     now_x, now_y = routine.pop() if (now_x, now_y) == (m, n): break for x, y in direction: if (x, y) != (-temp_x, -temp_y):             now_x += x             now_y += y             count += 1 if now_x &lt; 0 or now_x &gt; m or now_y &lt; 0 or now_y &gt; n:                 count -= 1                 now_x -= x                 now_y -= y continue else:                 temp_x, temp_y = x, y                 routine.append((now_x, now_y)) break if (now_x, now_y) != (m, n):     count = 0 if count != 0: print(count) else: print(-1)

广度搜索

暴力

可以计算出结果，为什么还是错呢

import random j=0 jie=[] while j&lt;=200: a=0 x = 0 y = 0 k = 0 g = 0 while x&lt;n: a = random.randint(0, 3) if a==1: x=1+x y=2+y k=k+1 elif a==2: x=2+x y=1+y g=g+1 chang=x kuan=y if chang==n and kuan==m: z=k+g jie.append(z) j=j+1 if jie==[]: print(-1) else: print(min(jie))

if n &gt; m:     n, m = m, n if n == 1 and m % 4 != 2: print(-1) elif n == m == 2: print(4) else: print((n+m) // 3 + abs(n+m) % 3)

纯数学方法，一开始弄了半天忘了2,2特例

st, d = [], [[1,2],[2,1],[1,-2],[-2,-1],[-1,2],[2,-1],[-1,-2],[-2,1]] for i in range(n+1):     st.append([0] * (m+1)) ans = 1000000000 def dfs(x, y, cnt): global ans if x == n and y == m: if cnt &lt; ans:             ans = cnt return for i in d: if x+i[0] &lt;= n and y+i[1] &lt;= m and x+i[0] &gt;= 0 and y+i[1] &gt;= 0 and st[x+i[0]][y+i[1]] == 0:             st[x+i[0]][y+i[1]] = 1             dfs(x+i[0], y+i[1], cnt+1)             st[x+i[0]][y+i[1]] = 0 st[0][0] = 1 dfs(0, 0, 0) print(ans if ans != 1000000000 else -1)

暴力搜索

什么东西执行成功提交却失败，这么废的吗

提交错误

<pre><code>plus=m+n if plus%3 == 0: a=int(plus/3) if(m &lt;= plus-a and n &lt;= plus-a) and (m &gt;= a and n &gt;= a): print(str(a)) elif (m==1 or n==1) and plus%3 != 0 : if m==1: if((n/2)%2==1): print(int(n/2)) elif n==1: if((m/2)%2==1): print(int(m/2)) else: print(&quot;-1&quot;) 原来的代码少了两种情况，加上了之后还是执行能通过但提交过不了</code></pre>

<pre><code>plus=m+n if plus%3 == 0:     a=int(plus/3) if(m &lt;= plus-a and n &lt;= plus-a) and (m &gt;= a and n &gt;= a): print(str(a)) else: print(&quot;-1&quot;)</code></pre>

执行代码过了但提交代码没过是什么鬼

#row_step*2 + col_step = m #row_step + col_step*2 = n

from sympy import * import re n = 5 m = 4 row_step = Symbol(&#x27;row_step&#x27;) col_step = Symbol(&#x27;low_step&#x27;) result = solve([row_step*2 + col_step-m,row_step + col_step*2-n],[row_step,col_step]) result_row_step = result[row_step] result_col_step = result[col_step] if re.search(&#x27;/&#x27;, str(result_col_step)) and re.search(&#x27;/&#x27;, str(result_row_step)): print(&#x27;-1&#x27;) else: print(result_col_step+result_row_step)

sympy模块能正确计算，但是找不到模块

<pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'宋体';font-size:12.0pt;">import numpy as np

def solveyima(n,m):
 a = np.array([[2,1],[1,2]])
 bl = [n,m]
 b = np.array(bl)
 x = np.linalg.solve(a,b)
 if x[0] &gt; 0 and x[1]&gt;0 and x[0]%1 == 0 and x[1]%1 == 0:
 return int(x[0] + x[1])
 else:
 return -1</pre>

用矩阵思想简单

def arrival(x,y,m,n): &nbsp;&nbsp;&nbsp; if x==m and y == n: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 1 &nbsp;&nbsp;&nbsp; else:return 0 def run(m,n,b,a=[],x=1,y=1,road=([1,2],[2,1],[1,-2],[2,-1])): &nbsp;&nbsp;&nbsp; try: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for i in range(4): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [i1, i2] = road[i] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if x + i1 &lt;= m and x + i1 &gt; 0 and y + i2 &lt;= n and y + i2 &gt; 0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x=x+i1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; y=y+i2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a.append(i+1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if arrival(x, y, m, n): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # print('至少需要走的步数为：%d，\n具体走法如下：' %len(a),a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b.append(len(a)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; run(m,n,x=x,y=y,b=b,a=a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x = x - i1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; y = y -i2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a.pop() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # break &nbsp;&nbsp;&nbsp; except RuntimeError:print('棋盘过大') def start(m,n): &nbsp;&nbsp;&nbsp; b=[] &nbsp;&nbsp;&nbsp; run(m, n, b) &nbsp;&nbsp;&nbsp; if&nbsp; b: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; print('至少需要走的步数为：%d'%min(b)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return min(b) &nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; print('没有结果返回') &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return -1 start(m,n)

第24题：一马当先

LTC-男人八题之八：电梯调度

斐波那契数列

勇气的挑战

因数（来自2013年ACM-ICPC世界总决赛）