灯泡游戏

时间限制: 1 Sec 内存限制: 64 MB
提交: 22 解决: 9
[提交][状态][讨论版]

题目描述

有一个n行m列的矩阵，左上角坐标是(0,0)，右下角坐标是(n-1,m-1)。每个格子有一个字符， “0”至“9”表示数字0至9，“a”至“z”表示数字10至35，“A”至“Z”表示数字36至61。矩阵的每个格子都有一个灯泡，刚开始除了左上角的灯泡是亮的，其他的灯泡都是灭的，刚开始你的得分是0。
游戏的过程是这样的：每次选一个灯泡是亮的格子X，同时选一个灯泡是灭的格子Y，而且要求格子X和格子Y是相邻的格子。这个步骤会使你的得分增加，增加的值是：格子X与格子Y代表的数字的差的绝对值。当然，这个步骤会使你选中的灭的灯泡变亮。重复上述操作，直到所有的灯泡都变成亮的。问你的最大得分是多少？

输入

第1行：两个整数n和m(1≤n，m≤50)。
　　接下来是n行m列的矩阵。
　　

输出

　　一个整数，表示最大得分。
　　

样例输入

2  2
05
aB

样例输出

提示

第一次选择：格子(0，0)和格子(1，0)，得分是10-0=10；第二次选择：格子(1，0)和格子(1，1)，得分是37-10：27；第三次选择：格子(1，1)和格子(0，1)，得分是37-5=32，因此总得分是：10+27+32=69。

这次题主要是构建图。又学到一招，二维数组构建新图，用hash 值建图。

#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#define fi first
#define se second
#define pi pair<int,int>
#define md make_pair
#define ha pair<int,pair<int,pi> >
using namespace std;
const int inf=0x3f3f3f3f;
char s[55][55];
int f[3000];
int cnt=0,sum,vis[3000][3000],dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
struct node {
    int x,y,w;
} nd[5000];
int change(char ch){
    if(ch>='0'&&ch<='9')    return ch-'0';
    else if(ch>='a'&&ch<='z')   return ch - 'a' +10;
    else return ch- 'A'+36;
}
void build(int n,int m){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int nx,ny;
            for(int z=0;z<4;z++){
                nx=i+dx[z],ny=j+dy[z];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){
                    int x=i*55+j,y=nx*55+ny;
                    if(!vis[x][y]){
                        //printf("%d %d %d 
",cnt,x,y);
                        nd[cnt].x=x,nd[cnt].y=y;
                        nd[cnt].w=abs(change(s[i][j])-change(s[nx][ny]));
                        vis[x][y]=1;vis[y][x]=1,cnt++;
                    }
                }
            }
        }
    }
}
bool cmp( node a,node b){
        return a.w>b.w;
}
int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void kruscal(int n,int m){
    for(int i=0;i<3000;i++){
        f[i]=i;
    }
    int c=0,num=0;
    while(c<cnt){
        int x=find(nd[c].x),y=find(nd[c].y);
        if(x!=y){
            f[x]=y;
            sum+=nd[c].w;
            num++;
        }
        if(num>=n*m-1) break;
        c++;

    }
    printf("%d
",sum);
}
int main()
{
    //freopen("data.in","r",stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%s",s[i]);
    build(n,m);
    //for(int i=0;i<cnt;i++)printf("%d ",nd[i].w);printf("
");
    sort(nd,nd+cnt,cmp);
    //for(int i=0;i<cnt;i++)printf("%d ",nd[i].w);printf("
");
    kruscal(n,m);
    return 0;
}