信息学奥赛一本通 1416：【17NOIP普及组】棋盘 | 洛谷 P3956 [NOIP2017 普及组] 棋盘

【题目链接】

洛谷 P3956 [NOIP2017 普及组] 棋盘
ybt 1416：【17NOIP普及组】棋盘

【题目考点】

1. 深搜：深搜回溯

2. 深搜剪枝：最优化剪枝

【解题思路】

搜索从左上角到右下角的所有走法中花费金币最少的走法。
需要使用深搜回溯，搜索从一点出发到另一点的所有路径。
设二维数组mp记录每个格子的颜色，如果无色记为-1，1是黄色，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：深搜

#include<bits/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]，到i，j的最小钱数 
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;
	else
		mc[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是sx，sy周围的位置 
		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;
	else
		cout << mc[m][m];
	return 0;
}