题1：area
描述：编程计算由“1”号围成的下列图形的面积。面积计算方法是统计“1”所围成的闭合曲线
中水平线和垂直线交点的数目。如下图所示，在 10*10 的二维数组中，有“1”围住了15个点，
因此面积为15。
【样例输入】
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
【样例输出】
15
思路：在“1”里面的“0”不好数，所以可以选择找补集，即“1”的个数和外部“0”的个数。
“1”的个数可以在输入时直接统计个数。而外部的“0”因为周围会和别的“0”连起来，所以
可以用递归统计。为防止“1”将外部的“0”割裂开，可以在外圈在加一圈“0”保证外圈“0”
连通在一起。
代码：
#include<bits/stdc++.h>
using namespace std;
int Map[12][12]={0},sum1=0,sum2=1,sum;
void Shu(int x,int y){
if(Map[x][y+1]==0&&y+1<=11){
Map[x][y+1]=1;
Shu(x,y+1);
sum2+=1;
}
if(Map[x+1][y]==0&&x+1<=11){
Map[x+1][y]=1;
Shu(x+1,y);
sum2+=1;
}
if(Map[x][y-1]==0&&y-1>=0){
Map[x][y-1]=1;
Shu(x,y-1);
sum2+=1;
}
if(Map[x-1][y]==0&&x-1>=0){
Map[x-1][y]=1;
Shu(x-1,y);
sum2+=1;
}
return ;
}
int main(){
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
scanf("%d",&Map[i][j]);
if(Map[i][j]==1){
sum1+=1;
}
}
}
Map[0][0]=1;
Shu(0,0);
/*for(int i=0;i<=11;i++){
for(int j=0;j<=11;j++){
printf("%d ",Map[i][j]);
}
printf("\n");
}*/
/*for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
if(Map[i][j]!=1){
sum++;
}
}
}*/
printf("%d %d\n",sum1,sum2);
printf("%d\n",144-sum1-sum2);
return 0;
}
题2：奇怪的电梯
【问题描述】
大楼的每一层楼都可以停电梯，而且第 i 层楼（1<=i<=N）上有一个数字 Ki（0<=Ki<=N）。
电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果
不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5 代表了 Ki（K1=3,K2=3,......），从一
楼开始。在一楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有-2 楼。那么，
从 A 楼到 B 楼至少要按几次按钮呢？
【输入格式】
输入文件共有二行，第一行为三个用空格隔开的正整数，表示 N,A,B(1≤N≤200, 1 ≤
A,B≤N)，第二行为 N 个用空格隔开的正整数，表示 Ki。
【输出格式】
输出文件仅一行，即最少按键次数,若无法到达，则输出-1。【输入样例】
5 1 5
3 3 1 2 5
【输出样例】
3
思路：深搜，没了
代码：
#include<bits/stdc++.h>
using namespace std;
int N,a,b,l,sum=0,ans=10001;
int E[201],A[201]={0};
void dfs(int x){
if(x==b){
ans=min(ans,sum);
return;
}
if(sum>=ans){
return;
}
A[x]=1;
if(x+E[x]<=N&&A[x+E[x]]==0){
sum++;
dfs(x+E[x]);
sum--;
}
if(x-E[x]>=1&&A[x-E[x]]==0){
sum++;
dfs(x-E[x]);
sum--;
}
A[x]=0;
}
int main(){
scanf("%d%d%d",&N,&a,&b);
for(int i=1;i<=N;i++){
scanf("%d",&E[i]);
}
dfs(a);
if(ans==10001){
printf("-1");
}
else{
printf("%d",ans);
}
return 0;
}
题3：产生数（Produce）（洛谷P1037）
【问题描述】
给出一个整数 n（n<=2000）和 k 个变换规则（k≤15）。规则：
① 1 个数字可以变换成另 1 个数字；
② 规则中，右边的数字不能为零。
例如：n=234，k=2 规则为
2 → 5
3 → 6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）234，534，264，564 共 4
种不同的产生数。
求经过任意次的变换（0 次或多次），能产生出多少个不同的整数。仅要求输出不同整
数个数。
【输入格式】
n
k
x1 y1
x2 y2
... ...
xn yn
【输出格式】
格式为一个整数（满足条件的整数个数）。
【输入样例】
234
2
2 5
3 6
【输出样例】
4
思路：因为整数的每一位互不影响，根据乘法定律，只需要找出每一位数字有多少种可能
乘在一起即可（原型也算）。寻找可能性的时候要注意：若1->2 2->3，则1可以变3
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
char c[4];
int k,shu[5],sum=1;
scanf("%s%d",&c,&k);
int l=strlen(c);
for(int i=0;i<l;i++){
shu[i+1]=c[i]-'0';
}
int s[10]={0};
bool zhongzhuan[10][10]={0};
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
zhongzhuan[x][y]=1;
}
for(int p=0;p<10;p++){
for(int i=0;i<10;i++){
zhongzhuan[i][i]=1;
for(int j=1;j<10;j++){
if(zhongzhuan[i][p]&&zhongzhuan[p][j]){
zhongzhuan[i][j]=1;
}
}
}
}
for(int i=1;i<=l;i++){
for(int j=0;j<=9;j++){
if(zhongzhuan[shu[i]][j]==1){
s[i]+=1;
}
}
sum*=s[i];
}
/*for(int i=1;i<=l;i++){
printf("%d",shu[i]);
}printf("\n");*/
printf("%d\n",sum);
return 0;
}
题4：家庭问题
【问题描述】
有 n 个人，编号为 1,2,......n，另外还知道存在 K 个关系。一个关系的表达为二元组（α，
β）形式，表示α，β为同一家庭的成员。
当 n，k 和 k 个关系给出之后，求出其*有多少个家庭、最大的家庭中有多少人？
例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(4,5)
此时，6 个人组成三个家庭，即：｛1,2,3｝为一个家庭，｛4,5｝为一个家庭，｛6｝单独为
一个家庭，第一个家庭的人数为最多。【输入格式】
文件的第一行为 n,k 二个整数（1≤n≤100）（用空格分隔）
接下来的 k 行，每行二个整数（用空格分隔）表示关系
【输出格式】
二个整数（分别表示家庭个数和最大家庭人数）
【输入样例】
6 3
1 2
1 3
4 5
【输出样例】
3 3
思路：一对一对判断。如果都是之前没出现的人，就建一个新家；如果有之前出现的人，另一
个人之前没出现，就将新人放进旧人的家。注意：判断后仍没有家的人需要一人一个家
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
scanf("%d%d",&n,&k);
int f[n+1],t=0,c[n+1],Max=0;
memset(f,0,sizeof(f));memset(c,0,sizeof(c));
for(int i=0;i<k;i++){
int a,b;
scanf("%d%d",&a,&b);
if(c[a]==0&&c[b]==0){
t+=1;
f[t]=1;
c[a]=t;c[b]=t;
f[t]+=1;
Max=max(Max,f[t]);
}
else if((c[a]!=0&&c[b]==0)||(c[a]==0&&c[b]!=0)){
int p;
if(c[a]!=0){
p=c[a];
c[b]=p;
}
else{
p=c[b];
c[a]=p;
}
f[p]+=1;
Max=max(f[p],Max);
}
}
for(int i=1;i<=n;i++){
if(c[i]==0){
t+=1;
f[t]=1;
Max=max(Max,f[t]);
}
}
printf("%d %d\n",t,Max);
return 0;
}