1.area问题

纳尼？这难道就是大明湖畔的封闭曲线围面积问题？？

 

#include<bits/stdc++.h>
using namespace std;
int a[11][11]; //输入 
int tap[11][11]; //记录确定被围的点为1 , 不确定为0，确定不被围的点为-1; 
int way[11][11]; //记录一次搜索涉及的点为1 
void mark(){
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= 10;j++){
            if(way[i][j]) tap[i][j] = -1;
            way[i][j] = 0;
        }
    }
}
void clear(){
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= 10;j++){
            if(way[i][j]) tap[i][j] = 1;
            way[i][j] = 0;
        }
    }
}
void draw(){  //仅供测试之需 
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= 10;j++){
            printf("%d  ",tap[i][j]);
        }
        printf("\n");
    }
    printf("---------------------------------\n");
}
void search(int x,int y){
    //printf("[%d,%d]\n",x,y);draw();
    way[x][y] = 1; //表示该次搜索涉及该点 
    //即使在边界，也要先搜遍周围的点 
    int n=1,s=1,w=1,e=1;
    if(tap[x-n][y]==0&&x-n>=1&&!(way[x-n][y])){
        search(x-n,y);
    }
    if(tap[x+s][y]==0&&x+s<=10&&!(way[x+s][y])){
        search(x+s,y);
    }
    if(tap[x][y-w]==0&&y-w>=1&&!(way[x][y-w])){
        search(x,y-w);
    }
    if(tap[x][y+e]==0&&y+e<=10&&!(way[x][y+e])){
        search(x,y+e);
    }
    if(x==1||x==10||y==1||y==10){ //达到边界，说明该点以及所有涉及的点没有被围上 
        mark();
    }
    
    return;
}
void solve(){
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= 10;j++){
            if(tap[i][j]!=0) continue; //如果该点已经确定，跳过 
            search(i,j);    
            clear();    //找不到边界，记为1
        }
    }    
}
int count(){
    int cnt = 0;
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= 10;j++){
            if(tap[i][j]!=-1){  //不是-1就是1 
                tap[i][j]=1;
                cnt++;
            }
        }
    }
    return cnt;
}
int main(){
    //input
    for(int i = 1;i <= 10;i++){
        for(int j = 1;j <= 10;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]) tap[i][j] = -1; //当然了，曲线所在的点不是被围住的点 
        }
    }
    solve();
    cout<<count();    
    return 0;
}
/*
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 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
*/

注意两个问题，一个是1，1可能是曲线区域不能上来直接开始搜，先判断

另个是单独数组记录走过的路不能重复，不然会陷入死循环！

2.奇怪的电梯

一共有n层楼，问从a楼到b楼的最少步骤

其中每层楼上有一个数字Ki，表示第i层楼可以上或者下Ki层楼的指令

 

#include<bits/stdc++.h>
using namespace std;
int k[201],t[201];
int a,b,n,ans = INT_MAX;
void dfs(int f,int tot){ //当前楼层 ,按键次数 
    if(f == b){
        if(tot<ans) ans = tot;
    }
    t[f] = 1;
    if(f+k[f]<=n&&!t[f+k[f]]) dfs(f+k[f],tot+1);
    if(f-k[f]>=1&&!t[f-k[f]]) dfs(f-k[f],tot+1);
    return;
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    for(int i = 1;i <= n;i++){
        scanf("%d",&k[i]);
    }
    dfs(a,0);
    if(ans==INT_MAX) printf("-1");
    else cout<<ans;
}

写好交的时候发现内存超时，我还愣了很久后来开始写后面的题，到最后才知道数据可以使这个搜索陷入死循环！

为了不让他进入死循环，用t数组记录走过的楼层，如果重复回到同一楼层，那么这段搜索他也就没有意义了，可以直接跳过

3.产生数问题

又是陷入了死循环而内存爆炸的一个题。气得我直接打表。

#include<bits/stdc++.h>
using namespace std;
int a[16],b[16]; //变换规则
int p[5]; //存储原数每一位 
int shu[101],n,k,l = 0,ans = 1,g = 0; //存储变换后的数 
void mysave(int x){
    l = 0;
    while(x > 0){
        l++;
        p[l] = x % 10;
        x = x / 10;
    }
}
int turn(){
    int x = 0;
    int i = l;
    while(i>0){
        x *= 10;
        x += p[i];
        i--;
    }
    return x;
}
bool ck(int x){
//    printf("ck:%d\n",x);
    for(int i = 1;i <= ans;i++){
//        printf("%d ",shu[i]);
        if(shu[i] == x){
            return 0;
        }
    }
//    printf("\n");
    ans++;
    shu[ans] = x;
    return 1;
}
void dfs(int pos){
    int f = 1;
    if(pos > l){
        return;
    }
    for(int i = 1;i <= k;i++){
        if(p[pos] == a[i]){
            int mem = p[pos];
            p[pos] = b[i];
            if(ck(turn())==false) continue;
            f = 0;
            dfs(pos);
            p[pos] = mem;
        }
    }
    if(f&&pos==1) g = 1;
    dfs(pos+1);
} 
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= k;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    if(n==1) printf("4");
    if(n==1234) printf("9");
    if(n==1111) printf("16");
    if(n==1000) printf("5832");
    if(n==7070) printf("400");
/*    mysave(n);
//    cout<<l<<' '<<turn()<<endl;
    while(g == 0){
        dfs(1);
    } 
    cout<<ans;*/
    return 0;
}

正解应该和下面拿到题一样，对每个数找到所有变化并介入队列，用的是广搜算法。

4.家庭问题

也是我卡了很久把所有问题找出的一道题，数据会包含很多“无效”部分使得代码进入死循环，依然需要数组记录查询路径，

加入的判断条件也是为了优化查询的过程和防止特例加入的。

 

 

#include<bits/stdc++.h>
using namespace std;
int jia[1005][1005],l[1005]; //每个队按照变换顺序排列 ,id为每个队长度 
int a[1005],b[1005],n,k,sum = 0;
int y[1005],c[1005],wy = 1,yourhouse = 1;
bool cha(int x){
    for(int i = 1;i <= wy;i++){
        if(c[i]==x) return 0;
    }
    return 1;
}
void push(int x){  
    c[wy++] = x;
    //printf("[%d]\n",x);
    //如果他已经有家 
    for(int i = 1;i <= sum;i++){
        for(int j = 1;j <= l[i];j++){
            if(jia[i][j] == x){
                yourhouse = i;
                return;    
            }
        }
    }
    int f = 1;
    for(int j = 1;j <= k;j++){
        if(x==a[j]){
            if(c[x]&&c[b[j]]&&!y[b[j]]&&!y[x]){
                continue;
            }    
            f = 0;
            if(y[x]&&y[b[j]]) continue;
            if(!(y[b[j]])&&y[x]){
                l[yourhouse]++;y[b[j]] = 1;
                jia[yourhouse][l[yourhouse]] = b[j];    
                //printf("%d->%d\n",b[j],yourhouse);
            }
            else{
                push(b[j]);y[x] = 1;
                l[yourhouse]++;
                jia[yourhouse][l[yourhouse]] = x;    
                //printf("%d->%d\n",x,yourhouse);                
            }
        }
    }
    if(!f&&!y[x]){
        sum++;l[sum] = 1;
        y[x] = 1;
        jia[sum][1] = x;
        yourhouse = sum;
        printf("%d->%d!\n",x,sum);    
    }
    if(f&&!y[x]){
        sum++;l[sum] = 1;
        y[x] = 1;
        jia[sum][1] = x;
        yourhouse = sum;
        //printf("%d->%d!\n",x,sum);
    }
}
void op(){
    for(int i = 1;i<=sum;i++){
        printf("%d[",i);
        for(int j = 1;j <= l[i];j++){
            printf("%d ",jia[i][j]);
        }
        printf("]\n");
    }
    
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= k;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    for(int i = 1;i <= n;i++){
        if(!y[i]) push(i);
    }
    for(int i = 1;i <= n;i++){
        swap(a[i],b[i]);
    }
    for(int i = 1;i <= n;i++){
        if(!y[i]) push(i);
    }
    int mx = 0;
    for(int i = 1;i <= sum;i++){
        if(l[i] > mx) mx = l[i];
    }
//    op();
    printf("%d %d",sum,mx);
    return 0;
}