上周日的题解居然拖到现在才写……

上周六去蹭算法课顺便蹭了作业，搜索我一向比较弱……

A：hdu1010

Tempter of the Bone

走迷宫，问能否恰好k步从起点走到终点。

其实不难但是搞了很久，第二个剪枝还是看网上的题解才知道的。

典型的深搜，有两个减枝

1.当前的步数加上最少的到终点的步数大于了k，不可能走得到

2.当前的步数加上最少的到终点的步数减去k为奇数，也不可能走得到（简单地说就是（假设s在t的左边）只要向左走了一步就一定得向右走一步回到那一列）

#include#include#include#include
#include
using namespace std;
const long k[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int flag;
long n,m,t;
long sx,sy,tx,ty;

bool a[10][10];
void init()
{
    memset(a,0,sizeof(a));

    for(long i=1;i<=n;i++) for(long j=1;j<=m;j++) { char c; cin>>c;
        if (c=='S') {sx=i;sy=j;a[i][j]=true;}
        if (c=='D') {tx=i;ty=j;a[i][j]=true;}
        if (c=='.') {a[i][j]=true;}
    }
}
void dfs(long x,long y,long d)
{
    if (flag) return;
    if((d==t)&&(x==tx)&&(y==ty)){ flag=true;return;}
    if (d>=t) return;
    long dis=abs(x-tx)+abs(y-ty);

    if((dis>t)||(dis+t-d)%2!=0) return;
    a[x][y]=false;
    for (long i=0;i!=4;i++)
    {
        long tmpx=x+k[i][0];
        long tmpy=y+k[i][1];
        if ((a[tmpx][tmpy]))
        {
            a[tmpx][tmpy]=false;
            //cout<>n>>m>>t;
    while ((n!=0)&&(m!=0)&&(t!=0))
    {
        init();
        if((abs(tx-sx)+abs(ty-sy))>t)
            {cout<<"NO"<>n>>m>>t;
    }

    return 0;

}

B：hdu1204：

Asteroids!

一个三维空间的广搜。

#include#include#includeusing namespace std;
struct point
{
    long x,y,z;
};
const long k[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
long n;
point s,t;
bool a[12][12][12];
long d[12][12][12];
point du[1040]={0};
long l=1,r=1;

void init()
{
    memset(a,0,sizeof(a));
    memset(d,0,sizeof(d));
    for(long k=0;k>c;
        if (c=='O') {a[i][j][k]=true;}
        if (c=='X') {a[i][j][k]=false;}
    }
    cin>>s.x>>s.y>>s.z;
    cin>>t.x>>t.y>>t.z;
}

long bfs(point s)
{
    du[r++]=s;
    a[s.x][s.y][s.z]=false;
    d[s.x][s.y][s.z]=0;
    while (l>s1>>n)
    {
       // cout<>s1;

    }

    return 0;

}

Oil Deposits

#include#include#include#include
#include
using namespace std;
long n,m;
char a[200][200];
void init()
{
    memset(a,0,sizeof(a));

    for(long i=1;i<=n;i++) for(long j=1;j<=m;j++) { cin>>a[i][j];
        if (a[i][j]=='@')
           a[i][j]=1;
        else a[i][j]=0;
    }
}
void change(long i,long j)
{
    long k,l;
    a[i][j]=0;
    if(a[i-1][j]>0)  change(i-1,j);
    if(a[i+1][j]>0)  change(i+1,j);
    if(a[i][j-1]>0)  change(i,j-1);
    if(a[i][j+1]>0)  change(i,j+1);
    if(a[i-1][j-1]>0)  change(i-1,j-1);
    if(a[i+1][j+1]>0)  change(i+1,j+1);
    if(a[i-1][j+1]>0)  change(i-1,j+1);
    if(a[i+1][j-1]>0)  change(i+1,j-1);
}


int main()
{
    
    cin>>n>>m;
    while ((n!=0)&&(m!=0))
    {
        init();

        long cnt=0;
        for(long i=1;i<=n;i++) for(long j=1;j<=m;j++) { if (a[i][j]!=0) { change(i,j); cnt++; } } cout<>n>>m;
    }

    return 0;

}

Substrings

大意：求若干个串的最长公共串的长度（可以正向也可以是反向的）

方法就是拿最短的串从长度为1的每个子串（或者这个子串的反向串）与其他的串做匹配，如果成功就增加长度，失败就将子串起点后移

#include#include#include#includeusing namespace std;
string a[110];
string s1;
long t,n;

void init()
{
    cin>>n;
    for(long i=0;i>a[i];
    }
    s1=a[0];
    long tmp=0;
    for(long i=1;imaxn) maxn=j;
        }
    }
    cout<>t;

    for (long i=1;i<=t;i++) { init(); find_max(); } return 0; }