题意:一个m*m的棋盘,上面有n个点,每个点有自己的颜色,其余的点是无色。要求是从(1,1)到(m,m)花费最少多少? 其中跨越的两个点如果颜色相同不花费,如果颜色不同则需要1¥,如果施展膜法效果-可以把下一个点把为指定的颜色,同时花费2¥。
思路: 题目状态很明确,当前的坐标x,y、当前的花费cost、当前是否使用魔法can。 之后就是常规的走棋盘,不过需要剪枝一下不然会TLE。 最简单的剪枝思路就是
1.记忆化搜索-记录当前坐标的最小花费,如果多次经过x,y并发现当前cost大于最小花费即return
2.最优性剪枝-如果当前cost > 当前最优解 剪掉。
// luogu-judger-enable-o2 #include <cstdio> #include <cstring> #include <queue> int n,m,x,y,c,cost; int Min = 19260817; int ax[4]={0,0,-1,1}; int ay[4]={1,-1,0,0}; int yh[105][105]; int Cost[105][105],Map[105][105]; bool vis[105][105]; void dfs(int x,int y,bool Can){ if(cost < yh[x][y]) yh[x][y] = cost; else return; if(x == m && y == m){ Min = cost; return; } for(int i = 0; i < 4; i++){ int nx = x + ax[i]; int ny = y + ay[i]; if(vis[nx][ny] || nx > m || ny > m || nx < 1 || ny < 1) continue; if(Map[nx][ny] != 0){ vis[nx][ny] = true; if(Map[x][y] == Map[nx][ny]) dfs(nx, ny, false); else{ if(cost + 1 >= Min){ vis[nx][ny] = false; continue; } cost++; dfs(nx, ny, false); cost--; } vis[nx][ny] = false; } else{ if(Can == true) continue; if(cost + 2 >= Min) continue; Map[nx][ny] = Map[x][y]; cost += 2; vis[nx][ny] = true; dfs(nx, ny, true); vis[nx][ny] = false; Map[nx][ny] = 0; cost -= 2; } } } void Read(){ scanf("%d%d",&m,&n); for(int i = 1; i <= n; ++i){ scanf("%d%d%d",&x,&y,&c); Map[x][y] = c + 1; } vis[1][1] = 1; memset(yh, 0x3f3f3f, sizeof(yh)); } int main(){ Read(); dfs(1, 1, 0); if(Min == 19260817) printf("-1\n"); else printf("%d\n", Min); return 0; }