A题：给你一个图，里面有坏草莓，让你吃蛋糕，不能吃坏草莓所在的行和列，问你最多能吃多少块蛋糕。
这题感觉还是贪心的做法吧，根据题目给的图，先从行开始，把没有草莓的行都吃掉，然后从列开始，把没有草莓的列吃掉。
代码：
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 2005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
int r[20],col[20];
int main()
{
int n,m;
char s[20];
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j]=='S')
{
r[i]=1;
col[j+1]=1;
}
}
}
int sum=0;
int allr=0;
for(int i=1;i<=n;i++)
{
if(r[i]==0)
{
sum+=m;
allr++;
}
}
for(int j=1;j<=m;j++)
{
if(col[j]==0)
{
sum+=(n-allr);
}
}
cout<<sum<<endl;
return 0;
}
B题：给你点和不能连的边，问你连最少的边，使任意一个点到其他点的距离都小于等于2。
把一个点连到其他所有的点就行了，开始还以为要用并查集，暴搜什么的，唉～～～水了。
代码：
#include<iostream>
#include<cstring>
#define maxn 1005
#define INF 0xfffffff
using namespace std;
int map[maxn][maxn];
int vis[maxn];
int main()
{
int n,m,a,b,i,j;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
vis[a]=vis[b]=1;
}
for( i=1;i<=n;i++)
{
if(vis[i]==0)
break;
}
cout<<n-1<<endl;
for( j=1;j<=n;j++)
{
if(i!=j)
cout<<i<<' '<<j<<endl;
}
return 0;
}
Ｃ题：给你一个图，一些点不能涂色，没涂一个点，它的上下左右四个方向都可以被涂色。
直接从每行，每列开始搜，如果存在某个点所在的行和列都没有可以涂色的位置，则输出－１。
然后分别行优先开始涂，列优先开始涂，求最小值。
代码：
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 105
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
int r[maxn],c[maxn];
char a[maxn][maxn];
int main()
{
int n;
cin>>n;
int flag1=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cin>>a[i][j];
if(a[i][j]=='.')
{
r[i]++;
c[j]++;
}
}
}
int flag=0;
for(int i=1; i<=n; i++)
{
if(r[i]==0)
flag1=1;
for(int j=1; j<=n; j++)
{
if(r[i]==0&&c[j]==0)
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag==1)
{
cout<<-1<<endl;
return 0;
}
int count=0;
if(flag1==0)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(a[i][j]=='.')
{
cout<<i<<' '<<j<<endl;
count++;
break;
}
}
}
}
else
{
for(int j=1;j<=n;j++)
{
for(int i=1;i<=n;i++)
{
if(a[i][j]=='.')
{
cout<<i<<' '<<j<<endl;
break;
}
}
}
}
return 0;
}
Ｄ题：给你一个图，一个人想走到出口，其他人想阻拦他，问你这个人要和多少个人打架。
从出口开始ｂｆｓ，在出口到先走到出口的人最短距离之内的所有人都要和他打架。
代码：
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 1005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
char map[maxn][maxn];
bool vis[maxn][maxn];
int n,m,sum,count;
int X[]={-1,1,0,0};
int Y[]={0,0,-1,1};
struct node
{
int x,y,step;
};
bool inmap(int x,int y)
{
if(0<=x&&x<n&&0<=y&&y<m)
return true;
else
return false;
}
void bfs(int sx,int sy)
{
queue<node>q;
node s;s.x=sx,s.y=sy,s.step=0;
node tmp;
q.push(s);
vis[sx][sy]=1;
while(!q.empty())
{
tmp=q.front(),q.pop();
int tx=tmp.x,ty=tmp.y,ts=tmp.step;
if(map[tx][ty]=='S')
{
count=tmp.step;
}
//cout<<tx<<' '<<ty<<' '<<tmp.step<<' '<<count<<endl;
if(tmp.step<=count&&map[tx][ty]!='E'&&map[tx][ty]!='S')
{
//cout<<tx<<' '<<ty<<' '<<map[tx][ty]<<endl;
sum+=(int)(map[tx][ty]-'0');
}
for(int i=0;i<4;i++)
{
int nx=tx+X[i],ny=ty+Y[i];
if(inmap(nx,ny)&&vis[nx][ny]==0&&map[nx][ny]!='T')
{
vis[nx][ny]=1;
tmp.x=nx,tmp.y=ny,tmp.step=ts+1;
if(tmp.step<=count)
q.push(tmp);
}
}
}
}
int main()
{
int i,j,sx,sy;
scanf("%d%d",&n,&m);
for( i=0;i<n;i++)
{
scanf("%s",map[i]);
for(j=0;j<m;j++)
{
if(map[i][j]=='E')
{
sx=i,sy=j;
}
}
}
count=INF;
sum=0;
bfs(sx,sy);
printf("%d\n",sum);
return 0;
}
Ｅ题：构造一个图，不含原图的边，并且新图边数与原图边数相同。
用随机数构造验证的方法，并设置构造次数。