ARTS Week 4
2024-09-01 20:08:07
标题： ARTS Week 4
分类： ARTS
tags： ARTS
Nov 18, 2019 ~ Nov 24, 2019
Algorithm
深入优先搜索-马遍历棋盘
要求：给定一个n * m的棋盘，左上角为(0, 0)，马的初始位置为(x, y)，找到所有方案使得马不重复地遍历棋盘，输出所有方案
思路
马走‘日’字，因此有八种移动方案，分别为：
dir = [[-2,1], [-1,2], [1,2], [2,1], [2,-1], [1,-2], [-1,-2], [-2,-1]]
坐标(x, y)移动一步后的结果为(x+dir[i][0], y+dir[i][1])
马的移动需要受到以下两个条件的约束:
- 移动后的点仍要在棋盘上，即
$ 0 \leq x+dir[i][0] \leq n-1 \(
\) 0 \leq y+dir[i][1] \leq m-1 $ - 移动后的点是要为访问过的，即
$ visited[x+dir[i][0]][y+dir[i][1]] $
实现
Python的实现代码如下：
def draw():
print('第', ans,'种方案：',history)
def horse(x, y, step):
if step == num:
global ans, found
ans = ans + 1
found = True
draw()
else:
for i in range(8):
x_temp = x + dir[i][0]
y_temp = y + dir[i][1]
if 0 <= x_temp < n and 0 <= y_temp < m and visited[x_temp][y_temp] == 0:
history[step] = [x_temp, y_temp]
visited[x_temp][y_temp] = 1
horse(x_temp, y_temp, step+1)
visited[x_temp][y_temp] = 0
Review
Emacs is Sexy
文章介绍的Emacs好处和安装Emacs
- Why
- 安装
- GNU/Linux：包管理器中就包含有Emacs
- Mac OS X：可以通过Homebrew或者Emacs For Mac OS X
- Windows：GNU官方
希望能开箱即用的用户，可以采用Spacemacs。至于 Spacemacs 如何安装，可以看我的这篇文章：Spacemacs 简单介绍及安装
Tips
python3 输入一行数字中间用空格相隔的读取方法，例如：s = '1 2 3 4 5'，如何提取为数组 nums = [1,2,3,4,5]
#方法1
num = [int(n) for n in input().split()]
#方法二
num = list(map(int, input().strip().split()))
print(num)
Share
最新文章
- 【Java并发系列04】线程锁synchronized和Lock和volatile和Condition
- 基于Deep Learning 的视频识别方法概览
- antmate.css
- 从resfful API设计到加密算法
- SPSS数据分析—广义估计方程
- jquery验证手机号码和固定电话号码
- BZOJ3322 : [Scoi2013]摩托车交易
- ubuntu 14.04 https 形式安装docker 私有库 harbor
- PHP使用1个crontab管理多个crontab任务
- 2014多校第一场J题 || HDU 4870 Rating（DP || 高斯消元）
- 开源的连接池技术DBCP和C3P0
- Jenkins master在windows
- Java基础(6)- 面向对象解析
- 【端-iOS】给iOS开发入门者编码的一点建议
- 如何改变XCode的默认设置
- Nginx failing to load CSS and JS files (MIME type error)
- 【CSS/JS】如何实现单行／多行文本溢出的省略（...）--老司机绕过坑道的正确姿势
- py-day3-4 python 匿名函数
- 如何在ubuntu系统里面用新加装的硬盘对系统进行扩容
- Java技术栈