第二周特训

1.poj 2312

迷宫类问题，用搜索解决。关键在于从起点开始类推到每个点的最短距离，所以搜索的条件要从visit数组变化，即若使到目标点的最少步数减少则将该点放入搜索列表（这个很重要）。关于存储数组我是这么办的，用二维整形数组存，一开始都置0（代表不通行），记得留边界（这样就不怕走出去了）。然后将‘B’付2，‘R'和‘S’不管（还是0），其余付1，这样算法也好写一些。我用的BFS，但我画了个3*3的表从（1,1）到（3,3）感觉好像DFS也可以，没试过。

#include"stdio.h"
#include"string.h"


struct set
{
    int x;
    int y;
};

struct line
{
    set a[100000];
    int in;
    int out;
};


line L;


void init()
{
    L.in=L.out=0;
}

void in(set e)
{
    if(L.in+1==L.out)
        return;
    L.a[L.in++]=e;
    L.in%=100000;
}

void out(set&e)
{
    if(L.in==L.out)
        return;
    e=L.a[L.out++];
    L.out%=100000;
}

    int least[310][310];
    int pos[310][310];

int main()
{
    set start,end,e,e1;
    int l,c,i,j;
    char ch;
    init();
    scanf("%d%d",&l,&c);
    while(l!=0)
    {
        getchar();
        memset(pos,0,100000);
        for(i=1;i<=l;i++)
        {
            for(j=1;j<=c;j++)
            {
                pos[i][j]=1;
                least[i][j]=1000000;
                scanf("%c",&ch);
                if(ch=='Y')
                    start.x=i,start.y=j;
                if(ch=='T')
                    end.x=i,end.y=j;
                if(ch=='R'||ch=='S')
                    pos[i][j]=0;
                if(ch=='B')
                    pos[i][j]=2;
            }
            getchar();
        }
        in(start);
        least[start.x][start.y]=0;
        while(L.in!=L.out)
        {
            out(e);
            for(i=1;i<=4;i++)
            {
                switch(i)
                {
                case 1:
                    e1.x=e.x;
                    e1.y=e.y+1;
                    break;
                case 2:
                    e1.y=e.y;
                    e1.x=e.x+1;
                    break;
                case 3:
                    e1.x=e.x;
                    e1.y=e.y-1;
                    break;
                case 4:
                    e1.x=e.x-1;
                    e1.y=e.y;
                    break;
                }
                if(pos[e1.x][e1.y]==0)
                    continue;
                if(least[e.x][e.y]+pos[e1.x][e1.y]<least[e1.x][e1.y])
                {
                    in(e1);
                    least[e1.x][e1.y]=least[e.x][e.y]+pos[e1.x][e1.y];
                }
            }
        }
        if(least[end.x][end.y]==1000000)
            printf("-1");
        else
            printf("%d\n",least[end.x][end.y]);
        scanf("%d%d",&l,&c);
        init();
    }
}

 

2.POJ 1321

在一个棋盘上放棋子，每行每列最多只能放一个，且棋盘不规则，问多少种放法。

有点像N皇后问题，变异的有点厉害。区别：1.棋盘不规则 2.没有每斜行不能放两个的规则 3.不一定每行都有棋子（就是这个让我费解了好一会儿）。所以算法也有改变，先保留用一个整型数组表示每列是否有棋子的做法，递归的搜索范围也要扩展到整个二维数组。因为棋子之间没有区别，所以可以每次递归从下一行第一个开始，避免重复，也省略了行重复问题。总的来说简单了些，虽然挺花时间的。

#include"stdio.h"
#include"string.h"



struct ss
{
    char s[20];
};

ss G[20];

int t[20];
int l;
int N;
int m;


void fun(int n,int p)
{
    if(n>=m)
    {
        N++;
        return;
    }
    int i,j;
    for(i=p;i<=l;i++) for(j=1;j<=l;j++)
        if(G[i].s[j]=='#'&&t[j]==0)
        {
            t[j]=1;
            fun(n+1,i+1);
            t[j]=0;
        }
}


int main()
{
    int i;
    scanf("%d%d",&l,&m);
    getchar();
    while(l!=-1)
    {
        memset(t,0,80);
        for(i=1;i<=l;i++)
            gets(G[i].s+1);
        N=0;
        fun(0,1);
        printf("%d\n",N);
        scanf("%d%d",&l,&m);
        getchar();
    }
}

3.problem G-POJ 2907

从一点出发经过数点后回到该点，确定次序使得总路程最短

问题直接解决有问题，采用深搜递归每当找到所有顶点就计算是否比当前最小值小，若是则改变最小值，否则不变，直到所有方案都结束。

#include"stdio.h"
#include"string.h"


int leap[200][200];
int color[200][200];
int visit[200][200];
int fn;
int l,c,crnum;


void fun(int n)
{
    int i,j,k,p,q,t;
    for(k=1,i=1;i<=l;i++)
        for(j=1;j<=c;j++)
            if(visit[i][j]==0)
                k=0;
    if(k==1&&n<fn)
    {
        fn=n;
        return;
    }
    for(i=1;i<=crnum;i++)
    {
        for(j=1;j<=l;j++) for(k=1;k<=c;k++)
            if(color[j][k]==i&&visit[j-1][k]==1&&visit[j][k]==0)
            {
                for(p=k+1;color[j][p]=color[j][k];p++);
                for(q=k+1
                visit[j][k]=1;
                leap[j][k]=n;
            }
        fun(n+1);
        for(j=1;j<=l;j++) for(k=1;k<=c;k++)
            if(leap[j][k]==n)
                visit[j][k]=0;
    }
}


int main()
{
    int N,M,x1,y1,x2,y2,cr,i,j;
    scanf("%d",&N);
    while(N--)
    {
        scanf("%d",&M);
        l=0,c=0,crnum=0;
        while(M--)
        {
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&cr);
            if(x2>l)
                l=x2;
            if(y2>c)
                c=y2;
            if(cr>crnum)
                crnum=cr;
            for(i=x1+1;i<=x2;i++) for(j=y1+1;j<=y2;j++)
                color[i][j]=cr;
        }
        memset(visit,0,150000);
        for(i=1;i<200;i++)
            visit[0][i]=1;
        fn=100000;
        fun(0);
        printf("%d\n",fn);
    }
}

problem H  -POJ 2251

迷宫问题：一个三维的空间里，求从起点到终点的最短路程。

同problem A 一样，重要的是一个数组标识从起点到该点的最短距离。只不过是三位的而已。

 

#include"stdio.h"


struct sss
{
    char s[50][50];
};

struct node
{
    int l,r,c;
};

struct line
{
    node a[30000];
    int in;
    int out;
}L;

void init()
{
    L.in=L.out=0;
}

void in(node e)
{
    if(L.in+1==L.out)
        return;
    L.a[L.in++]=e;
    L.in%=30000;
}

void out(node&e)
{
    if(L.in==L.out)
        return;
    e=L.a[L.out++];
    L.out%=30000;
}

sss G[50];
int least[50][50][50];


int main()
{
    node start,end,e,e1;
    int l,r,c,i,j,k;
    int a[6]={1,-1,0,0,0,0};
    int b[6]={0,0,1,-1,0,0};
    int d[6]={0,0,0,0,1,-1};
    scanf("%d%d%d",&l,&r,&c);
    while(l!=0)
    {
        getchar();
        init();
        for(i=0;i<50;i++) for(j=0;j<50;j++) for(k=0;k<50;k++)
            G[i].s[j][k]='#';
        for(i=1;i<=l;i++)
        {
            for(j=1;j<=r;j++)
            {
                for(k=1;k<=c;k++)
                {
                    G[i].s[j][k]=getchar();
                    if(G[i].s[j][k]=='S')
                        start.l=i,start.r=j,start.c=k;
                    if(G[i].s[j][k]=='E')
                        end.l=i,end.r=j,end.c=k;
                }
                getchar();
            }
            getchar();
        }
        in(start);
        for(i=1;i<50;i++) for(j=1;j<50;j++) for(k=1;k<50;k++)
            least[i][j][k]=100000;
        least[start.l][start.r][start.c]=0;
        while(L.in!=L.out)
        {
            out(e);
            for(i=0;i<6;i++)
            {
                e1.l=e.l+a[i];
                e1.r=e.r+b[i];
                e1.c=e.c+d[i];
                if(least[e.l][e.r][e.c]+1<least[e1.l][e1.r][e1.c]&&G[e1.l].s[e1.r][e1.c]!='#')
                {
                    least[e1.l][e1.r][e1.c]=least[e.l][e.r][e.c]+1;
                    in(e1);
                }
            }
        }
        if(least[end.l][end.r][end.c]==100000)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n",least[end.l][end.r][end.c]);
        scanf("%d%d%d",&l,&r,&c);
    }

}

problem I -POJ 2708

给一个n*n的有数子宫，可以对每行执行操作（将最后一个变成第一个，其余往右移），使得最大值（每一列的和，其中最大的和）最小。

通过完全模拟，深搜来实现。每次完成一次操作都计算最大值，若最大值小于当前最小值则替换，否则继续，直到全部情况都完成。

#include"stdio.h"


int G[10][10];
int value[10];
int min;
int c;


void fun(int a[])
{
    int i,t;
    for(i=c,t=a[c];i>=2;i--)
        a[i]=a[i-1];
    a[1]=t;
}


void dfs(int n)
{
    int i,j,m;
    if(n>c)
    {
        for(i=1;i<=c;i++)
            for(j=1,value[i]=0;j<=c;j++)
                value[i]+=G[j][i];
        m=value[1];
        for(i=2;i<=c;i++)
            if(value[i]>m)
                m=value[i];
        if(m<min)
            min=m;
        return;
    }
    for(i=1;i<=c;i++)
    {
        if(i!=1)
            fun(G[n]);
        dfs(n+1);
    }
}


int main()
{
    int i,j;
    scanf("%d",&c);
    while(c!=-1)
    {
        for(i=1;i<=c;i++) for(j=1;j<=c;j++)
            scanf("%d",&G[i][j]);
        min=100000;
        dfs(1);
        printf("%d\n",min);
        scanf("%d",&c);
    }
}