面试随缘刷题--day7

如果前面scanf("%d %d",&n,&k),后面无论char c是c=getchar()还是scanf("%c",&c);在遇到 3 5换行这种情况的时候都会把换行符号都进去

但如果是char c[100]然后scanf("%s",c)这种时候会坚持到第一个非换行（也非空格）再读取。getchar都可以读，你要是中间加一个getchar然后好几个换行或者空格，他还是会读取不是的第一个哦。

kuangbin简单搜索专题

poj 1321棋盘问题(dfs)

棋盘不是规则的，要在有空位的地方放东西
放的数量是不固定的，因此存在某一行不放东西的可能性，注意这个的sum不要受到前面的影响（所以前面不可对sum操作)
判断出结果要用sum==k判断，但不能直接return，否则后面可能存在的此行不放东西的情况会被忽略
当前是sum或者当前index=n+1都是边界退出判断，因为当前已经sum了代表后面必定都不放。
当前行指定不放东西，对行数=index只要走一次支路就是可以的了，所以这个要放在循环外面
sum=k的ans++判断在哪里用都可以（如果在放置的瞬间，注意不要返回，如果在判断边界的时候，注意不要跟index==n+1混在一起）

#include
#include<string.h>
#include
using namespace std;
int chess[10][10];
int n,k;
int ans=0;
int hashline[10];
void generate(int index,int sum)
{
    if(sum==k)
        ans++;
    if(index==n+1 || sum==k)
        return;
    for(int i=1;i<=n;i++)
    {
        if(chess[index][i]==1 && hashline[i]==0 )
        {
            hashline[i]=1;
            /*if(sum+1==k)
            {
                ans++;
            }*/
            generate(index+1,sum+1);
            hashline[i]=0;
        }
    }
    generate(index+1,sum);
}
int main()
{
    while(scanf("%d%d",&n,&k) && n!=-1)
    {
        for(int i=1;i<=n;i++)
        {
            getchar();
            for(int j=1;j<=n;j++)
            {
                char c=getchar();
                if(c=='#')
                    chess[i][j]=1;
                else
                    chess[i][j]=0;
            }
        }
        ans=0;
        memset(hashline,0,sizeof(hashline));
        generate(1,0);
        printf("%d\n",ans);
    }
    return 0;
}

poj 2251 Dungeon Master(bfs)

入队的结构体是包含step和坐标的，但是基础存数据用三维数组就好啦。
入队的条件是没有入队过，当前点无障碍（如果end是特殊标记也含end），也不会超过地图边界
读取某个点后记得出队，start点不要忘了pd
每一个点要像他的四周扩张，如果可以的话，下一个点的step是他的+1
到没有其他的点，仍然没找到答案，那就是没有答案。

#include
#include
#include<string.h>
using namespace std;
int roadmap[32][32][32];
int l,r,c;
int startx,starty,startz,endx,endy,endz;
int pd[32][32][32]={0};
struct node{
    int x;
    int y;
    int z;
    int step;
}a[30000];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
bool bianjie(int x,int y,int z)
{
    if(x>=1 && x<=l  && y>=1 &&y<=r && z>=1 && z<=c && pd[x][y][z]==0 && roadmap[x][y][z]==0|| roadmap[x][y][z]==3)
        return true;
    return false;
}
int ans=-1;
void bfs()
{
    queueq;
    node start;
    start.x=startx;
    start.y=starty;
    start.z=startz;
    start.step=0;
    pd[startx][starty][startz]=1;
    q.push(start);
    while(!q.empty())
    {
        node tempnode=q.front();
        q.pop();
        for(int i=0;i<=5;i++)
        {
            int tempx=tempnode.x+x[i];
            int tempy=tempnode.y+y[i];
            int tempz=tempnode.z+z[i];
            if(bianjie(tempx,tempy,tempz))
            {
                //printf("%d %d %d\n",tempx,tempy,tempz);
                if(tempx==endx && tempy==endy && tempz==endz)
                {
                    ans=tempnode.step+1;
                    return;
                }
                pd[tempx][tempy][tempz]=1;
                node temp;
                temp.x=tempx;
                temp.y=tempy;
                temp.z=tempz;
                temp.step=tempnode.step+1;
                q.push(temp);
            }
        }
    }
}
int main()
{
    while(scanf("%d %d %d",&l,&r,&c) && l!=0)
    {
        memset(pd,0,sizeof(pd));
        ans=-1;
        for(int i=1;i<=l;i++)
        {
            getchar();
            for(int j=1;j<=r;j++)
            {
                for(int z=1;z<=c;z++)
                {
                    char temp=getchar();
                    if(temp=='.')
                    {
                        roadmap[i][j][z]=0;
                    }
                    else if(temp=='#')
                    {
                        roadmap[i][j][z]=1;
                    }
                    else if(temp=='S')
                    {
                        startx=i;
                        starty=j;
                        startz=z;
                        roadmap[i][j][z]=2;
                    }
                    else if(temp=='E')
                    {
                        endx=i;
                        endy=j;
                        endz=z;
                        roadmap[i][j][z]=3;
                    }
                }
                getchar();
            }
        }
        bfs();
        if(ans==-1)
        {
            printf("Trapped!\n");
        }
        else
            printf("Escaped in %d minute(s).\n",ans);
    }
    return 0;
}

面试随缘刷题--day7

相关

标签