建设网站的费用明细,缓存图片 wordpress,营销型外贸网站制作,宝塔做网站443链接【题目链接】
洛谷 P3956 [NOIP2017 普及组] 棋盘 ybt 1416#xff1a;【17NOIP普及组】棋盘
【题目考点】
1. 深搜#xff1a;深搜回溯
2. 深搜剪枝#xff1a;最优化剪枝
【解题思路】
搜索从左上角到右下角的所有走法中花费金币最少的走法。 需要使用深搜回溯…【题目链接】
洛谷 P3956 [NOIP2017 普及组] 棋盘 ybt 1416【17NOIP普及组】棋盘
【题目考点】
1. 深搜深搜回溯
2. 深搜剪枝最优化剪枝
【解题思路】
搜索从左上角到右下角的所有走法中花费金币最少的走法。 需要使用深搜回溯搜索从一点出发到另一点的所有路径。 设二维数组mp记录每个格子的颜色如果无色记为-11是黄色0是红色。 在某次搜索时当前位置为(sx, sy)下一个要访问的位置为(x, y)已经使用金币coin。 如果当前位置(sx,sy)是有色的
如果下一个位置(x,y)是有色的 如果二者颜色相同到下个位置时花的金币数coin不变如果颜色不同到下个位置花的金币数coin加1。 如果下一个位置(x,y)是无色的 将下一个位置通过魔法变为与(sx, sy)同色到下个位置的金币数coin加2
如果当前位置(sx, sy)是无色的但是变成了col色。那么下个位置(x, y)不可以是无色的。 如果下个位置(x,y)是有色的那么
如果(x,y)位置的颜色和col相同那么到下个位置时花的金币数coin不变如果(x,y)位置的颜色和col不同到下个位置花的金币数coin加1。
设二维数组mc,mc[i][j]表示到达(i, j)位置时花的最少金币数。 最优性剪枝如果到(sx, sy)位置花的钱数coin比已知的一种到(sx, sy)位置的走法花钱mc[sx][sy]相等或更多则没必要再搜索了直接返回。 这里必须进行最优性剪枝否则搜索会超时。
【题解代码】
解法1深搜
#includebits/stdc.h
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
int m, n, mp[N][N], minCoin INF, mc[N][N];//mp[i][j]:为1代表黄色0代表红色-1代表无色 mc[i][j]到ij的最小钱数
int dir[4][2] {{0,1},{0,-1},{-1,0},{1,0}};
bool vis[N][N];
void dfs(int sx, int sy, int coin, int col)//col:如果(sx,sy)本来是无色col为(sx,sy)通过魔法变化后的颜色
{if(coin mc[sx][sy])//最优化剪枝如果到当前位置花的钱数比已知的一种到当前位置的走法花钱更多则没必要再搜索了。 return;elsemc[sx][sy] coin;if(sx m sy m)//到达终点点 return; for(int i 0; i 4; i){int x sx dir[i][0], y sy dir[i][1];//x,y是sxsy周围的位置 if(x 1 x m y 1 y m !vis[x][y]){vis[x][y] true;if(mp[sx][sy] 1 || mp[sx][sy] 0)//如(sx, sy)是红黄 {if(mp[x][y] -1)//如果下一个位置无色 dfs(x, y, coin 2, mp[sx][sy]);//变成与出发点相同的颜色 else if(mp[x][y] mp[sx][sy])//颜色相同 dfs(x, y, coin, -1);else//颜色不同 dfs(x, y, coin 1, -1);}else if(mp[sx][sy] -1 mp[x][y] ! -1)//如(sx, sy)是无色 {//如果无色的下一个格子还是无色则不访问 if(mp[x][y] col)//颜色相同 dfs(x, y, coin, -1); else//颜色不同 dfs(x, y, coin 1, -1);}vis[x][y] false;}}
}
int main()
{int x, y, c;memset(mp, -1, sizeof(mp));cin m n;for(int i 1; i n; i){cin x y c;mp[x][y] c;}memset(mc, 0x3f, sizeof(mc));dfs(1, 1, 0, -1);if(mc[m][m] INF)cout -1;elsecout mc[m][m];return 0;
}
