bfs();
int ans=0;
// printf("%d\n",dp[s.x][s.y]);
for(int i=1;i<=n;i++) //最短距离小的话，就直接加上
for(int j=1;j<=m;j++)
if(save[i][j]>'0'&&save[i][j]<='9'&&vis[i][j]&&dp[i][j]<=dp[s.x][s.y])
ans+=save[i][j]-'0';
printf("%d\n",ans);
}
return 0;
}
#include
#include
#include
#include
#include
#include
#include
#include
#include
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int dp[1100][1100],n,m;
char save[1100][1100];
bool vis[1100][1100];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct PP
{
int x,y;
};
PP s,e;
void bfs() //找到终点到任何一点的最短距离
{
queue
myq.push(e);
while(!myq.empty())
{
PP f=myq.front();
myq.pop();
for(int i=0;i<4;i++)
{
int xx=f.x+dir[i][0],yy=f.y+dir[i][1];
if((save[xx][yy]=='S'||(save[xx][yy]>='0'&&save[xx][yy]<='9'))&&!vis[xx][yy])
{
//printf(":%d %d\n",xx,yy);
vis[xx][yy]=true;
dp[xx][yy]=dp[f.x][f.y]+1;
myq.push((PP){xx,yy});
} //不在方格里的点为空的，不会扫描的
}
}
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=m;j++)
{
if(save[i][j]=='S')
s.x=i,s.y=j;
if(save[i][j]=='E')
e.x=i,e.y=j,dp[i][j]=0,vis[i][j]=true;
}
}
// printf("%d %d\n",e.x,e.y);
bfs();
int ans=0;
// printf("%d\n",dp[s.x][s.y]);
for(int i=1;i<=n;i++) //最短距离小的话，就直接加上
for(int j=1;j<=m;j++)
if(save[i][j]>'0'&&save[i][j]<='9'&&vis[i][j]&&dp[i][j]<=dp[s.x][s.y])
ans+=save[i][j]-'0';
printf("%d\n",ans);
}
return 0;
}
E. Graph Reconstruction
题目意思：
给一幅图，图中任意结点的度数至多为2。
让你重构一幅图，要求:图中节点和原来一样，边数数量也一样，任意节点度数至多为2.
解题思路：
题中所说的图的边数最多为n.
1、随机算法。
随机m个点，连成m条边，判断每一条边是否在给定的图里面，在的话，在随机，都不在，则满足题目要求，直接输出就行了。
2、构造法。
当n<=7,直接暴力判断
当n>7,一定存在一种构造满足题意。
构造方法：
因为每个点的度数最多为2，所以每一个联通块要么是一条线，要么是一个环，首先根据联通块将节点分成若干部分。
然后将每一部分的节点的奇数位置节点提前。（保证相同部分的相邻节点之间的连线不冲突）
然后选择一个节点数量最多的那个部分，如果其节点数为偶数的话，交换头两个节点（防止环的情况尾和首相连有冲突），最后将其余各部分的节点从前之后依次插入。
最后按照给定的边数，从前之后输出相邻的两个节点构成一条边，如果需要把最后一个节点和第一个节点连起来。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include