棋盘（noip2017普及组）

题目描述

有一个m \times 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：

输出样例#1：

输入样例#2：

输出样例#2：

-1

说明

输入输出样例 1 说明

从(1,1)(1,1)开始，走到(1,2)(1,2)不花费金币

从(1,2)(1,2)向下走到(2,2)(2,2)花费 11 枚金币

从(2,2)(2,2)施展魔法，将(2,3)(2,3)变为黄色，花费 22 枚金币

从(2,2)(2,2)走到(2,3)(2,3)不花费金币

从(2,3)(2,3)走到(3,3)(3,3)不花费金币

从(3,3)(3,3)走到(3,4)(3,4)花费 11 枚金币

从(3,4)(3,4)走到(4,4)(4,4)花费 11 枚金币

从(4,4)(4,4)施展魔法，将(4,5)(4,5)变为黄色，花费22 枚金币，

从(4,4)(4,4)走到(4,5)(4,5)不花费金币

从(4,5)(4,5)走到(5,5)(5,5)花费 11 枚金币

共花费 88枚金币。

输入输出样例 2 说明

从( 1, 1)(1,1)走到( 1, 2)(1,2),不花费金币

从( 1, 2)(1,2)走到( 2, 2)(2,2),花费11金币

施展魔法将( 2, 3)(2,3)变为黄色,并从( 2, 2)(2,2)走到( 2, 3)(2,3)花费22 金币

从( 2, 3)(2,3)走到( 3, 3)(3,3)不花费金币

从( 3, 3)(3,3)只能施展魔法到达( 3, 2),( 2, 3),( 3, 4),( 4, 3)(3,2),(2,3),(3,4),(4,3)

而从以上四点均无法到达( 5, 5)(5,5),故无法到达终点,输出-1−1

数据规模与约定

对于 330%的数据, 1 ≤ m ≤ 5, 1 ≤ n ≤ 101≤m≤5,1≤n≤10。

对于 60%的数据, 1 ≤ m ≤ 20, 1 ≤ n ≤ 2001≤m≤20,1≤n≤200。

对于 100%的数据, 1 ≤ m ≤ 100, 1 ≤ n ≤ 1,0001≤m≤100,1≤n≤1,000。

解析：

看到这个程序我首先想到的就是深度优先搜索，这样只能过部分数据，其他超时（TLE）。

#include<iostream>

using namespace std;

int chess[][]={};

int flag[][]={};

int dx[]={-,,,};

int dy[]={,,-,};

int m,n,total=;

int dgp(int x,int y,int color,int sum){

    if(x==m&&y==m&&sum<total){total=sum; return ;}

    for(int i=;i<=;i++){

        int xx=x+dx[i],yy=y+dy[i];

        if(!flag[xx][yy]&&chess[xx][yy]!=-&&(chess[x][y]!=||chess[xx][yy]!=)){

            flag[xx][yy]=;

            if(chess[xx][yy]==chess[x][y]||(chess[x][y]==&&color==chess[xx][yy]))dgp(xx,yy,chess[x][y],sum);

            else if(chess[xx][yy]==)dgp(xx,yy,chess[x][y],sum+);

                else dgp(xx,yy,chess[x][y],sum+);

            flag[xx][yy]=;

        }   }

}

int main(){

    int x,y,c;

    cin>>m>>n;

    for(int i=;i<=m+;i++) chess[i][]=chess[][i]=chess[m+][i]=chess[i][m+]=-;

    for(int i=;i<=m;i++)

        for(int j=;j<=m;j++)

            chess[i][j]=;

    for(int i=;i<=n;i++){

        cin>>x>>y>>c;

        chess[x][y]=c+;

    }

    flag[][]=;

    dgp(,,,);

    if (total==) cout <<-;

    else cout<<total;

    return ;

}

于是我添加了2个剪枝，竟然全部Ac，由此得出结论“暴力出奇迹，剪枝少不了！！！”

#include<iostream>

using namespace std;

int chess[][]={};// 棋盘

int flag[][]={};//访问标记

int dist[][]={}; //记录最短距离

int dx[]={-,,,};

int dy[]={,,-,};

int inf=;

int m,n,total=inf;

int dfs(int x,int y,int color,int sum){//记忆化搜索

    if (sum>=dist[m][m]) return  ;//剪枝1，如果到达当前点的距离已经大于等于终点

    if (dist[x][y]<=sum) return ;//剪枝2，如果到达当前点的距离不是当前最优。

    dist[x][y]=sum;//如果到达当前点的距离是当前最优

    if(x==m&&y==m&&sum<dist[m][m]){dist[m][m]=sum; return ;}//如果到达终点

    for(int i=;i<=;i++){

        int xx=x+dx[i],yy=y+dy[i];

        if(!flag[xx][yy]&&chess[xx][yy]!=-&&(chess[x][y]!=||chess[xx][yy]!=)){

            flag[xx][yy]=;//已经访问标记

            if(chess[xx][yy]==chess[x][y]||(chess[x][y]==&&color==chess[xx][yy])){dfs(xx,yy,chess[x][y],sum);}

            else if(chess[xx][yy]==){dfs(xx,yy,chess[x][y],sum+);}

                else {dfs(xx,yy,chess[x][y],sum+);}

            flag[xx][yy]=;//撤销访问标记，回溯。

        }   }

}

int main(){

    int x,y,c;

    cin>>m>>n;

    for(int i=;i<=m+;i++) chess[i][]=chess[][i]=chess[m+][i]=chess[i][m+]=-;//边界

    for(int i=;i<=m;i++)

        for(int j=;j<=m;j++)

            {chess[i][j]=;dist[i][j]=inf;}

    for(int i=;i<=n;i++){

        cin>>x>>y>>c;

        chess[x][y]=c+;

    }

    flag[][]=;//起点

    dfs(,,,);

    if (dist[m][m]==inf) cout <<-;

    else cout<<dist[m][m];

    return ;

}

巴特西