共 3 篇文章
传送门 思路 题目读完，很容易想到DFS的思路，很快就可以撸一个标准的dfs解法： ```cpp class Solution { public: int ans = INT_MAX; int minimumTimeRequired(vector& jobs, int k) { vector works(k); const int n = jobs.size(); dfs(0, works, jobs, 0, n, k); return ans; } void dfs(int now, vector& w, vector& j, int maxn, int n, …
传送门 题目大意 Flip Game是在一个4x4的矩形棋盘上进行的游戏，16个方格中的每一个方格上都放置了有两面的棋子。每块棋子的一面是白色的，另一面是黑色的。每一轮你都要翻转3到5个棋子，从而将其上边的颜色从黑色变为白色，反之亦然。每轮要翻转的棋子按照以下规则选择。 1、在16枚棋子中任选一枚。 2、将所选棋子和所有相邻棋子向左、向右、向上、向下翻转（如果有的话）。游戏的目标是翻转所有棋子白面朝上或所有棋子黑面朝上。你要写一个程序，寻找实现这个目标所需的最少回合数。 思路 一个棋子有且仅有两个状态，非黑即白。所以，对同一颗棋子而言，翻动偶数次显然是没有意义的，只有奇数次的翻动才会改变棋子状态，所以只用考虑第一次翻面操作。一共十六个格子，最多16步就能全部翻完，所以从0~16枚举每个操作，只要某一次成功了，这次的步数就是最优的。 用dfs来翻，如果到叶子节点还没成功就回溯。需要注意的是回溯需要把之前翻过的所有棋子翻回来。 代码 ```cpp #include #include using namespace std; int ans; bool flag; bool mp[5][5] = {0}; //方向数组: //左、右、下、上、中 const int dx[5] = {-1, 1, 0, 0, 0}; const int dy[5] = {0, 0, -1, 1, …
A 中国象棋 [图片缺失] 原图：https://img-blog.csdnimg.cn/20200506201533473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxMDMyMA==,size_16,color_FFFFFF,t_70#pic_center 一道挺标准的DFS模板，只不过走法换成了走日字。 ```cpp #include using namespace std; char g[10][9]; bool book[10][9]; int dx[] = { -2,-1,1,2,2,1,-1,-2 }; int dy[] = { 1,2,2,1,-1,-2,-2,-1 }; bool dfs(int x, int y) { book[x][y] = true; if (g[x][y] == 'T')return true; for (int i = 0; i < 8; …