P3956 棋盘
题目描述
有一个\(m×m\)的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1个金币。
另外， 你可以花费2个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
输入输出格式
输入格式：
第一行包含两个正整数\(m,n\) ，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的\(n\)行，每行三个正整数\(x, y, c\)， 分别表示坐标为\((x,y)\)的格子有颜色\(c\)。
其中\(c=1\)代表黄色，\(c=0\)代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为(1,1) ，右下角的坐标为\((m,m)\) 。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是(1,1) 一定是有颜色的。
输出格式：
一个整数，表示花费的金币的最小值，如果无法到达，输出-1 。
数据规模与约定
对于 30% 的数据, 1≤m≤5,1≤n≤10 。
对于 60% 的数据, 1≤m≤20,1≤n≤200 。
对于 100% 的数据, 1≤m≤100,1≤n≤1,000 。
这道题让我收获巨大。
首先，先入为主的，我想到了DP，初始态为左上角，终态为右下角，每个状态由它的左边和上面的点转移。
因为是否用了魔法也算作状态，所以DP方程设计的比较繁琐
令\(dp[i][j][k][l]\)代表\(i\)行\(j\)列颜色为\(k(1/0)\)是否使用魔法(\(l\)为0为没有使用)
转移直接看代码就行
code:
#include#include int min(int x,int y){return x
然而
最开始我以为是方程的某些细节错了（毕竟转移方程好麻烦啊），后来翻了洛谷上的一些题解才明白可以从右边或下面转。
那么状态转移方程似乎就不好设计了，因为不知道要先做谁啊。
翻了一下题解，大多是一些记搜或是搜索剪枝，但一个最短路建模吸引了我的注意。
于是\(Dijk\)的贪心思想出来了。
用二叉堆维护，每次取出答案最小的点去更新其他的点，则一定是正确的（图中无负边）
具体地，维护一个五元组\((x,y,col,is,w)\)，分别代表坐标，颜色，是否用膜法，当前答案，每次朝四个方向更新即可。
从我的理解来看，这道题把我对 Dijk，动态规划和广搜的理解放在了一起，让我感觉到它们有着本质上的相似，只是在基础上又加上了一些限制而已。
广搜：不管是否优秀都进行暴力的枚举
动态规划：基于Dijk的贪心使方程有了无后效性 Dijk：贪心的思想其实也基于了一种动态规划欢迎大家提出不足之处！
code:
#include#include #include using namespace std;const int M=105;const int X[5]={0,0,1,0,-1};const int Y[5]={0,1,0,-1,0};int g[M][M],m,n,used[M][M][2][2];struct node{ int x,y,col,is,w; bool friend operator <(node n1,node n2) { return n1.w>n2.w; } node(){} node(int x,int y,int col,int is,int w) { this->x=x;this->y=y;this->col=col; this->is=is;this->w=w; }};priority_queue q;int main(){ scanf("%d%d",&m,&n); int x0,y0,c; memset(g,-1,sizeof(g)); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x0,&y0,&c); g[x0][y0]=c; } node t0(1,1,g[1][1],0,0); q.push(t0); int ans=0x3f3f3f3f; while(!q.empty()) { node from=q.top(); q.pop(); int x=from.x,y=from.y,col=from.col,is=from.is,w=from.w; if(used[x][y][col][is]) continue; if(x==m&&y==m) {ans=w;break;} used[x][y][col][is]=1; for(int i=1;i<=4;i++) { int xx=X[i]+x,yy=Y[i]+y; if(xx==0||xx==m+1||yy==0||yy==m+1) continue; if(g[xx][yy]!=-1) { if(!used[xx][yy][g[xx][yy]][0]) { node tt(xx,yy,g[xx][yy],0,w+(col^g[xx][yy])); q.push(tt); } } else if(!is) { if(!used[xx][yy][col][1]) { node tt(xx,yy,col,1,w+2); q.push(tt); } } } } if(ans==0x3f3f3f3f) printf("-1\n"); else printf("%d\n",ans); return 0;}