P3956 [NOIP2017 普及组] 棋盘题解 » 老官童鞋gogo的博客

题目传送门

题解

题目理解与强调

题目给出一个$m \times m$的一个棋盘，每个格子有三种颜色状态：红色、黄色、无色。每次从$(1,1)$开始走，可以走上下左右四个方向，最终走到$(m,m)$。

当从一个格子走向另一个格子时，如果两个格子的颜色相同，那么不需要花费金币；如果不同，则需要花费$1$个金币。另外，可以花费$2$个金币让下一个无色格子暂时变为你指定的颜色。当离开这个格子后，颜色会重新变成无色，并且不能连续走两次无色的格子。

思路分析

思路简单：DFS或者BFS，本题个人认为DFS会更简单一些。

每次从当前点$x$搜索上下左右四个方向，设我要搜索的下一个格子为$y$，到达格点y的最小花费为$c[y]$，如果$y$符合以下要求就进入下一层递归搜索。

$y$在棋盘中。
若$x$为无色，则$y$不能为无色。

然后进行以下判断：

如果$x$的颜色与$y$的颜色相同，那么从$x$点转移到$y$点不需要花费金币，即$c[y]=min{c[x],c[y]}$。
如果$x$的颜色与$y$的颜色不相同，那么从$x$点转移到$y$点需要花费1$$金币，即$c[y]=min{c[x]+1,c[y]}$。
如果$y$为无色，那么就进行贪心，将$y$的颜色修改为与$x$相同的颜色。

第三条为什么可以这样贪心？如果$y$修改后与$x$颜色相同，那么这一步只需要花费$2$个金币，这时候$y$的下一步会出现两种情况，一种是与$x$颜色相同，一种是与$x$颜色不同，前者需要再花$1$个金币，后者不需要花费金币，那么最终结果可能是只花费$3$个或者$2$个金币。如果$y$修改后与$x$颜色不同，除了要花费变色的两个金币外，还要花费$1$个金币，这时候$y$的下一步还会出现上述的两种情况，那么最终结果是花费$4$个或者$3$个金币。这是不优的。

最后统计完答案输出即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 1000001
queue<pair<int,pair<int,int> > >q;
int m,n,co[101][101],c[101][101][3];
int d[2][5]={{0,1,-1,0,0},{0,0,0,1,-1}};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void dfs(int col,int x,int y,int p)
{
    for(int i=1;i<=4;i++)
    {
        int dx=x+d[0][i],dy=y+d[1][i];
        if(dx>m||dy>m||dx<1||dy<1)
            continue;
        if(co[dx][dy]==0&&p!=1&&c[x][y][col]+2<c[dx][dy][col])
        {
            c[dx][dy][col]=c[x][y][col]+2;
            dfs(col,dx,dy,1);
        }
        else if(co[dx][dy]==col&&c[x][y][col]+1<c[dx][dy][col])
        {
            c[dx][dy][col]=c[x][y][col];
            dfs(col,dx,dy,0);
        }
        else if(co[dx][dy]!=col&&co[dx][dy]!=0&&c[x][y][col]<c[dx][dy][col%2+1])
        {
            c[dx][dy][col%2+1]=c[x][y][col]+1;
            dfs(col%2+1,dx,dy,0);
        }
    }
}
int main()
{
    m=read(),n=read();
    memset(c,127,sizeof(c));
    c[1][1][0]=c[1][1][1]=c[1][1][2]=0;
    for(int i=i;i<n;i++)
    {
        int x=read(),y=read(),z=read();
        co[x][y]=z+1;
    }
    dfs(co[1][1],1,1,0);
    int ans=2139062143;
    for(int i=0;i<3;i++)
    {
        ans=min(c[m][m][i],ans);
    }
    if(ans==2139062143)
        cout<<"-1";
    else
        cout<<ans;
    return 0;
}

41ms 776.00KB