[NOIP2017 普及组] 棋盘(dfs记忆化搜索 | bfs优先队列双解法)
题目链接：[NOIP2017 普及组] 棋盘 - 洛谷
题目描述
有一个m×mm×m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 11个金币。
另外， 你可以花费 22 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
输入格式
第一行包含两个正整数m,nm,n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的nn行，每行三个正整数x,y,cx,y,c， 分别表示坐标为(x,y)(x,y)的格子有颜色cc。
其中c=1c=1 代表黄色，c=0c=0 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为(1,1)(1,1)，右下角的坐标为(m,m)(m,m)。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是(1,1)(1,1) 一定是有颜色的。
输出格式
一个整数，表示花费的金币的最小值，如果无法到达，输出−1−1。
输入输出样例
输入 #1
5 7 1 1 0 1 2 0 2 2 1 3 3 1 3 4 0 4 4 1 5 5 0
输出 #1
8
输入 #2
5 5 1 1 0 1 2 0 2 2 1 3 3 1 5 5 0
输出 #2
-1
思考一(dfs)：首先想到使用dfs查找所有可以走到终点的路径，并取其花费cost最小的路径。本题难点在于搜索中如何判断是否可以使用魔法，以及比较将要花费的金币情况。因此将坐标，当前花费金币数量，当前能否使用魔法 作为变量。判断将要走的方向是否需要使用魔法，不需要判断颜色是否相同，需要则判断能否使用魔法。代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int INF=999999;
int m,n,ans=INF;
int a[1010][1010];//为方便判断 使0为空白,1为黄色,2为红色
bool flag[1010][1010];
int tx[]={-1,1,0,0};
int ty[]={0,0,-1,1};
void dfs(int x,int y,int cost,int can)
{
if(x==m&&y==m)//到终点则寻找别可行的路径
{
ans=min(ans,cost);return;
}
for(int i=0;i<4;i++)
{
int xx=x+tx[i],yy=y+ty[i];
if(!flag[xx][yy]&&xx>=1&&xx<=m&&yy>=1&&yy<=m)
{
if(a[xx][yy]!=0)//如果不需要使用魔法
{
flag[xx][yy]=1;//因为下面一定会进入递归，因此在此标记此坐标已走过
if(a[xx][yy]==a[x][y])//如果颜色相同
dfs(xx,yy,cost,1);
else//如果颜色不同
dfs(xx,yy,cost+1,1);
flag[xx][yy]=0;//在此取消标记即可
}
else//如果必须使用魔法
{
if(can)//如果可以使用魔法(即上一个格子不为空)
{
flag[xx][yy]=1;
a[xx][yy]=a[x][y];
dfs(xx,yy,cost+2,0);
a[xx][yy]=0;
flag[xx][yy]=0;
}
}
}
}return;
}结果过一半TLE，因此考虑剪枝，因此使用数组记录每次走到的当前坐标的所花费的最小金币。类似记忆化搜索，实则为剪枝。
#include<iostream>
#include<cstring>
using namespace std;
int INF=999999;
int m,n,ans=INF;
int a[1010][1010];
bool flag[1010][1010];
int book[1010][1010];//记录数组，将其初始化为非常大的数
int tx[]={-1,1,0,0};
int ty[]={0,0,-1,1};
void dfs(int x,int y,int cost,int can)
{
if(x==m&&y==m)
{
ans=min(ans,cost);return;
}
if(cost>=book[x][y]) return;//如果当前消费已经超过历史上所走过此坐标的消费则直接返回
book[x][y]=cost;//否则记录并继续递归
for(int i=0;i<4;i++)
{
int xx=x+tx[i],yy=y+ty[i];
if(!flag[xx][yy]&&xx>=1&&xx<=m&&yy>=1&&yy<=m)
{
if(a[xx][yy]!=0)
{
flag[xx][yy]=1;
if(a[xx][yy]==a[x][y])
dfs(xx,yy,cost,1);
else
dfs(xx,yy,cost+1,1);
flag[xx][yy]=0;
}
else
{
if(can)
{
flag[xx][yy]=1;
a[xx][yy]=a[x][y];
dfs(xx,yy,cost+2,0);
a[xx][yy]=0;
flag[xx][yy]=0;
}
}
}
}return;
}
int main()
{
memset(book,0x3f,sizeof book);//初始化
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(!c)
a[x][y]=2;//2=red 1=yellow 0=null
else
a[x][y]=c;
}
dfs(1,1,0,1);
if(ans<INF) cout<<ans;
else cout<<"-1";
return 0;
} 思考二(bfs优先队列):使用小根堆队列使当前队列中花费最小的坐标来向四个方向探索。由于题意限制，每个坐标最多只走一次就可以达到最小消费，因此也要使用bool数组来标记走过的坐标。其核心处于dfs类似。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int INF=999999;
int m,n,ans=INF;
int a[1010][1010],book[1010][1010];
bool flag[1010][1010];
int tx[]={-1,1,0,0};
int ty[]={0,0,-1,1};
struct node{
int x,y,cost,can;
friend bool operator < (node a,node b)//运算符重载
{
return a.cost>b.cost;
}
};
void bfs()
{
priority_queue<node> que;//定义一个小根堆队列
que.push({1,1,0,1});
flag[1][1]=1;
while(!que.empty())
{
node t=que.top();que.pop();//flag[t.x][t.y]=0;//每次用队头搜索
if(t.x==m&&t.y==m)
ans=min(t.cost,ans);
for(int i=0;i<4;i++)
{
int xx=t.x+tx[i],yy=t.y+ty[i];
if(!flag[xx][yy]&&xx>=1&&xx<=m&&yy>=1&&yy<=m)
{
if(a[xx][yy])//如果将要搜索的格子有颜色
{
flag[xx][yy]=1;
if(a[xx][yy]==a[t.x][t.y])//如果颜色相同
que.push({xx,yy,t.cost,1});
else//如果不同
que.push({xx,yy,t.cost+1,1});
}
else//如果如果将要搜索的格子无颜色
{
if(t.can)//如果可以使用魔法
{
flag[xx][yy]=1;
que.push({xx,yy,t.cost+2,0});
a[xx][yy]=a[t.x][t.y];
}
}
}
}
}
}
int main()
{
memset(book,0x3f,sizeof book);
cin>>m>>n;
for(int i=0;i<n;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(!c) a[x][y]=2;//2=red
else a[x][y]=c;
}
bfs();
if(ans<INF)
cout<<ans;
else
printf("-1");
return 0;
}