灯泡游戏

灯泡游戏

时间限制: 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

样例输出

69

提示

第一次选择：格子(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 n",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("%dn",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("n");
sort(nd,nd+cnt,cmp);
//for(int i=0;i<cnt;i++)printf("%d ",nd[i].w);printf("n");

kruscal(n,m);
return 0;
}