2012-0092

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

一个比较简单的搜索，无论深搜宽搜都可以。
只要注意，整个山谷中所有雪球的位置周期是k，所以在山谷中某个点的时候，时间如果分别是t和t+k，对应的情况是等价的。
所以搜索的点的个数最大是n*m*k。
另外注意企鹅走的规则按照描述中的认认真真写进去就可以了，我都详细给图说明过了。

{{{
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=100,maxm=100,maxk=150;

char a[maxk][maxm];
bool visited[maxn][maxm][maxk];
int n,m,k;
bool found;
const int dx[3]={0,1,0};
const int dy[3]={1,0,-1};

inline int make(int x){
    while(x<0)x+=k;
    while(x>=k)x-=k;
    return x;
}

void go(int x,int y,int t){
    if(x<0||x>=n)return;
    if(y<0||y>m)return;
    if(visited[x][y][t%k])return;
    if(a[make(x-t)][y]=='O')return;
    visited[x][y][t%k]=true;
    //printf("x:%d y:%d t:%d\n",x,y,t);
    if(y==m){found=true;return;}
    for(int i=0;i<3;i++){
        go(x+dx[i],y+dy[i],t+1);
        if(found)return;
    }
    if(a[make(x-t-1)][y]!='O'){
        go(x-1,y,t+1);
        if(found)return;
        go(x,y,t+1);
    }
}

int main(){
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        //printf("%d %d %d\n",n,m,k);
        memset(visited,0,sizeof visited);
        found=false;
        for(int i=0;i<k;i++){
            scanf("%s",a[i]+1);
            a[i][0]='.';
            a[i][m+1]='.';
        }
        /*
        for(int i=0;i<k;i++){
            for(int j=0;j<=m+1;j++)
                printf("%c",a[i][j]);
            printf("\n");
        }
        */
        go(0,0,0);
        printf(found?"Go!\n":"Turn around!\n");
    }
}
}}}

一个比较简单的搜索，无论深搜宽搜都可以。

只要注意，整个山谷中所有雪球的位置周期是k，所以在山谷中某个点的时候，时间如果分别是t和t+k，对应的情况是等价的。

所以搜索的点的个数最大是n*m*k。

另外注意企鹅走的规则按照描述中的认认真真写进去就可以了，我都详细给图说明过了。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100,maxm=100,maxk=150;
char a[maxk][maxm];
bool visited[maxn][maxm][maxk];
int n,m,k;
bool found;
const int dx[3]={0,1,0};
const int dy[3]={1,0,-1};
inline int make(int x){
    while(x<0)x+=k;
    while(x>=k)x-=k;
    return x;
}
void go(int x,int y,int t){
    if(x<0||x>=n)return;
    if(y<0||y>m)return;
    if(visited[x][y][t%k])return;
    if(a[make(x-t)][y]=='O')return;
    visited[x][y][t%k]=true;
    //printf("x:%d y:%d t:%d\n",x,y,t);
    if(y==m){found=true;return;}
    for(int i=0;i<3;i++){
        go(x+dx[i],y+dy[i],t+1);
        if(found)return;
    }
    if(a[make(x-t-1)][y]!='O'){
        go(x-1,y,t+1);
        if(found)return;
        go(x,y,t+1);
    }
}
int main(){
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        //printf("%d %d %d\n",n,m,k);
        memset(visited,0,sizeof visited);
        found=false;
        for(int i=0;i<k;i++){
            scanf("%s",a[i]+1);
            a[i][0]='.';
            a[i][m+1]='.';
        }
        /*
        for(int i=0;i<k;i++){
            for(int j=0;j<=m+1;j++)
                printf("%c",a[i][j]);
            printf("\n");
        }
        */
        go(0,0,0);
        printf(found?"Go!\n":"Turn around!\n");
    }
}