灯泡游戏
题目传送门
题目描述：有一个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代表的数字的差
的绝对值。当然，这个步骤会使你选中的灭的灯泡变亮。重复上述操作，
直到所有的灯泡都变成亮的。问你的最大得分是多少？
见到本题的第一个想法：广搜？
大部分人卡在这里不知道怎么做了（我就卡了QWQ）
其实这道题还有另外一种想法：建图，然后排序，最后弄最大生成树
本体最难的就是建图，那该如何建图呢？？？
这就要用到方向数组了，我们用方向数组，把每个点跑一遍。 （细节；要用vis防止重边）
建图代码如下
void biuld(){
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
for(int k=0;k<4;k++) {
int nx=i+xx[k],ny=j+yy[k];
if(nx>0&&nx<=n&&ny>0&&ny<=m) {
int I=i*51+j,J=nx*51+ny;
if(!vis[I][J]) {
f[++cnt].u=I;
f[cnt].v=J;
f[cnt].w=abs(check(a[i][j])-check(a[nx][ny]));
vis[I][J]=true;
}
}
}
}
}
}当然本题还要将字符转成int类型 check 代码如下：
int check(char qwq){
if(qwq<='9'&&qwq>='0')return (qwq-'0');
if(qwq<='z'&&qwq>='a')return (qwq-'a'+10);
return (qwq-'A'+36);
}当然这道题是最好应该用kruskal来跑最小生成树的
而且要用并查集来判断祖先节点是否相同
如果还有细节不懂的话，就看下方的代码
代码献上；
#include<bits/stdc++.h>
using namespace std;
struct node{
int u,v,w;
}f[100001];//节点u,v建立一条权值为w的边
int n,m,fa[5001],cnt;//fa记录节点的祖先节点
bool vis[3001][3001];//判重边
char a[51][51];
int xx[]={0,0,1,-1};//方向数组 用来建边
int yy[]={1,-1,0,0};
int check(char qwq){
if(qwq<='9'&&qwq>='0')return (qwq-'0');
if(qwq<='z'&&qwq>='a')return (qwq-'a'+10);
return (qwq-'A'+36);
}
bool cmp(node x,node y){
return x.w>y.w;
}//排序
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}//找祖先
void merge(int x,int y){
fa[find(x)]=find(y);
}//并查集
void kruskal() {
int sum=0,num=0;//num记录边的数量 sum 为总权值
for(int i=0;i<cnt;i++) {
if(find(f[i].u)!=find(f[i].v)) {//祖先是否一样
sum+=f[i].w;
num++;
merge(f[i].u,f[i].v);
}
if(num>=n*m-1)break;//n*m个点有n*m-1条边时必联通
}
printf("%d",sum);
}
void biuld(){
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
for(int k=0;k<4;k++) {//方向
int nx=i+xx[k],ny=j+yy[k];
if(nx>0&&nx<=n&&ny>0&&ny<=m) {//是否超出图的范围
int I=i*51+j,J=nx*51+ny;
if(!vis[I][J]) {//是否重复
f[++cnt].u=I;
f[cnt].v=J;
f[cnt].w=abs(check(a[i][j])-check(a[nx][ny]));//计算权值
vis[I][J]=true;
}
}
}
}
}
}
int main(){
for(int i=1;i<=5001;i++)fa[i]=i;//初始化
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
biuld();
sort(f,f+cnt+1,cmp);//排序
kruskal();
return 0;
}都看到这了，点个赞不过分吧