/ Vijos / 题库 / Wappo /

题解

31 条题解

  • 2
    @ 2018-07-02 15:43:35

    写了400多行if else。。
    关于怪兽的行走逻辑:
    分两个阶段:
    走第一步,如果怪兽与你水平方向不一致,那么它会企图往竖直方向走使得它和你的水平方向一致,这时候有可能竖直方向有墙(没有墙就走过去进入第二阶段),那么它就会往水平方向再企图走,如果没有墙就走,否则就不动(然后不再走第二步)。这样就走完了第一步
    走第二步和走第一步一样都要重新考虑一遍方向。
    主要就是明白“优先级”和“可行性”两个东西怎么讨论。
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=1000000007;
    const double eps=1e-8;

    int n,m;
    int a[21][21];
    int b[21][21];
    struct node {
    int x,y,x2,y2,t;
    int pre;
    int d;
    int dir;
    // t为陷入陷阱后还剩几秒钟出来,t=0表示没陷入陷阱
    void operator=(node a) {
    x=a.x,y=a.y,x2=a.x2,y2=a.y2,t=a.t;
    pre=a.pre;
    d=a.d;
    dir=a.dir;
    }
    };
    bool vis[21][21][21][21][4];
    node q[400*400*3+1];
    // x,y,x2,y2,t
    int head,tail;
    int X,Y,X2,Y2,EX,EY;
    bool ok(int x,int y) {
    return 1<=x&&x<=n&&1<=y&&y<=m&&!b[x][y];
    }
    void print(node a) {
    vector<int> v;
    int steps=a.d;
    while (1) {
    if (a.pre==0) break;
    v.pb(a.dir);
    a=q[a.pre];
    //cout<<a.x<<" "<<a.y<<endl;
    }
    while (v.size()) {
    if (v.back()==1) cout<<"up"<<endl;
    if (v.back()==2) cout<<"left"<<endl;
    if (v.back()==3) cout<<"right"<<endl;
    if (v.back()==4) cout<<"down"<<endl;
    v.pop_back();
    }
    cout<<"total steps: "<<steps<<endl;
    }
    void work(int &x,int &y,int &x2,int &y2,node &tmp) {
    if (tmp.t) tmp.t--;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    }
    }
    if (!(x==EX&&y==EY)&&x==x2&&y==y2) return;
    if (!vis[tmp.x][tmp.y][tmp.x2][tmp.y2][tmp.t]) {
    vis[tmp.x][tmp.y][tmp.x2][tmp.y2][tmp.t]=1;
    q[++tail]=tmp;
    }
    }
    int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>m>>n;
    FOR(i,n) FOR(j,m) cin>>a[i][j];
    FOR(i,n) FOR(j,m) {
    char t='\n';
    while (t=='\n') cin>>t;
    if (t=='S') X=i,Y=j;
    else if (t=='W') b[i][j]=1;
    else if (t=='M') X2=i,Y2=j;
    else if (t=='E') EX=i,EY=j;
    }
    head=tail=1;
    q[1]=node{X,Y,X2,Y2,0,0,0,0};
    vis[X][Y][X2][Y2][0]=1;
    while (head<=tail) {
    node u=q[head++];
    if (u.x==EX&&u.y==EY) {
    print(u);
    return 0;
    }
    node tmp;
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&1)&&ok(tmp.x-1,tmp.y)&&!(tmp.x2==tmp.x-1&&tmp.y2==tmp.y)) {
    tmp.x--,tmp.dir=1;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&2)&&ok(tmp.x,tmp.y-1)&&!(tmp.x2==tmp.x&&tmp.y2==tmp.y-1)) {
    tmp.y--,tmp.dir=2;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&4)&&ok(tmp.x,tmp.y+1)&&!(tmp.x2==tmp.x&&tmp.y2==tmp.y+1)) {
    tmp.y++,tmp.dir=3;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&8)&&ok(tmp.x+1,tmp.y)&&!(tmp.x2==tmp.x+1&&tmp.y2==tmp.y)) {
    tmp.x++,tmp.dir=4;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    }
    cout<<"impossible"<<endl;
    return 0;
    }
    ```

  • 0
    @ 2023-07-20 10:43:25

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=1000000007;
    const double eps=1e-8;

    int n,m;
    int a[21][21];
    int b[21][21];
    struct node {
    int x,y,x2,y2,t;
    int pre;
    int d;
    int dir;
    // t为陷入陷阱后还剩几秒钟出来,t=0表示没陷入陷阱
    void operator=(node a) {
    x=a.x,y=a.y,x2=a.x2,y2=a.y2,t=a.t;
    pre=a.pre;
    d=a.d;
    dir=a.dir;
    }
    };
    bool vis[21][21][21][21][4];
    node q[400*400*3+1];
    // x,y,x2,y2,t
    int head,tail;
    int X,Y,X2,Y2,EX,EY;
    bool ok(int x,int y) {
    return 1<=x&&x<=n&&1<=y&&y<=m&&!b[x][y];
    }
    void print(node a) {
    vector<int> v;
    int steps=a.d;
    while (1) {
    if (a.pre==0) break;
    v.pb(a.dir);
    a=q[a.pre];
    //cout<<a.x<<" "<<a.y<<endl;
    }
    while (v.size()) {
    if (v.back()==1) cout<<"up"<<endl;
    if (v.back()==2) cout<<"left"<<endl;
    if (v.back()==3) cout<<"right"<<endl;
    if (v.back()==4) cout<<"down"<<endl;
    v.pop_back();
    }
    cout<<"total steps: "<<steps<<endl;
    }
    void work(int &x,int &y,int &x2,int &y2,node &tmp) {
    if (tmp.t) tmp.t--;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    else {
    if (y2<y) {
    if (!(a[x2][y2]&4)) {
    y2++;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (y2>y) {
    if (!(a[x2][y2]&2)) {
    y2--;
    if (b[x2][y2]) tmp.t=3;
    } else {
    if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    } else if (x2>x) {
    if (!(a[x2][y2]&1)) {
    x2--;
    if (b[x2][y2]) tmp.t=3;
    }
    } else if (x2<x) {
    if (!(a[x2][y2]&8)) {
    x2++;
    if (b[x2][y2]) tmp.t=3;
    }
    }
    }
    }
    }
    }
    if (!(x==EX&&y==EY)&&x==x2&&y==y2) return;
    if (!vis[tmp.x][tmp.y][tmp.x2][tmp.y2][tmp.t]) {
    vis[tmp.x][tmp.y][tmp.x2][tmp.y2][tmp.t]=1;
    q[++tail]=tmp;
    }
    }
    int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>m>>n;
    FOR(i,n) FOR(j,m) cin>>a[i][j];
    FOR(i,n) FOR(j,m) {
    char t='\n';
    while (t=='\n') cin>>t;
    if (t=='S') X=i,Y=j;
    else if (t=='W') b[i][j]=1;
    else if (t=='M') X2=i,Y2=j;
    else if (t=='E') EX=i,EY=j;
    }
    head=tail=1;
    q[1]=node{X,Y,X2,Y2,0,0,0,0};
    vis[X][Y][X2][Y2][0]=1;
    while (head<=tail) {
    node u=q[head++];
    if (u.x==EX&&u.y==EY) {
    print(u);
    return 0;
    }
    node tmp;
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&1)&&ok(tmp.x-1,tmp.y)&&!(tmp.x2==tmp.x-1&&tmp.y2==tmp.y)) {
    tmp.x--,tmp.dir=1;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&2)&&ok(tmp.x,tmp.y-1)&&!(tmp.x2==tmp.x&&tmp.y2==tmp.y-1)) {
    tmp.y--,tmp.dir=2;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&4)&&ok(tmp.x,tmp.y+1)&&!(tmp.x2==tmp.x&&tmp.y2==tmp.y+1)) {
    tmp.y++,tmp.dir=3;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    tmp=u;
    tmp.d++;
    tmp.pre=head-1;
    if (!(a[tmp.x][tmp.y]&8)&&ok(tmp.x+1,tmp.y)&&!(tmp.x2==tmp.x+1&&tmp.y2==tmp.y)) {
    tmp.x++,tmp.dir=4;
    work(tmp.x,tmp.y,tmp.x2,tmp.y2,tmp);
    }
    }
    cout<<"impossible"<<endl;
    return 0;
    }

  • 0
    @ 2009-10-11 20:15:28

    AC后的提示:

    (1)怪兽被困陷阱里到时间了以后如果没有移动不算再掉进去(那样就永远出不来了);

    (2)在人走之后要判断是否到终点(如果已到终点则不用考虑怪兽了,只不过有的Wappo版本里即使人走到终点也不算过关,需要怪兽进行最后一次操作,若没有抓到人才算过关)以及是否直接碰到怪兽(那不是自杀?)

    (3)怪兽在不能横着走的情况下会竖着走,如果不能竖着走的话就不动(怪兽有点SB,如果人在它左上角则它只会向左或向上)

  • 0
    @ 2009-10-06 21:50:46

    。。。疯了。。。

    为后人留下宝贵经验。。

    1.怪物掉进了陷阱后时间到不能接着再掉进去。。orz

    2.怪物掉进了陷阱时间到了如果没动不算再掉入

    3.如果是85分,记得在人走后先判是否到终点。。。

    。。如上种种。。。泪牛满面。。。

  • 0
    @ 2009-09-10 16:50:33

    在走出来之前不该再掉进去 应该说清楚点

  • 0
    @ 2009-07-06 12:14:03

    全是细节问题啊……

  • 0
    @ 2009-01-31 17:26:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    注意细节!!!!!!

    75行 C

  • 0
    @ 2008-10-29 12:58:01

    编译通过...

    ├ 测试数据 01:答案错误...程序输出比正确答案长

    ├ 测试数据 02:答案错误...程序输出比正确答案长

    ├ 测试数据 03:答案错误...程序输出比正确答案长

    ├ 测试数据 04:答案错误...程序输出比正确答案长

    ├ 测试数据 05:答案错误...程序输出比正确答案长

    ├ 测试数据 06:答案错误...程序输出比正确答案长

    ├ 测试数据 07:答案错误...程序输出比正确答案长

    ├ 测试数据 08:答案错误...程序输出比正确答案长

    ├ 测试数据 09:答案错误...程序输出比正确答案长

    ├ 测试数据 10:答案错误...程序输出比正确答案长

    ├ 测试数据 11:答案错误...程序输出比正确答案长

    ├ 测试数据 12:答案错误...程序输出比正确答案长

    ├ 测试数据 13:答案错误...程序输出比正确答案长

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:0 有效耗时:0ms

    看来细节很多!

    ?

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案错误...程序输出比正确答案长

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案错误...程序输出比正确答案长

    ├ 测试数据 07:答案错误...程序输出比正确答案长

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案错误...程序输出比正确答案长

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:69 有效耗时:0ms

    快疯了

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案错误...程序输出比正确答案长

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案错误...程序输出比正确答案长

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:85 有效耗时:0ms

    终于,苦尽甘来150行.............

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    总结经验:

    第一次,错的很白痴,略过;

    第二次,MONSTER从陷阱里出来后,如果没移动不会再进去;

    第三次,走到终点后没有直接输出,而是继续模拟;

    55555555,足可见细节之重要乎,吾之AC率飞流直下三千尺矣!

  • 0
    @ 2007-09-28 00:11:56

    数据错得一塌糊涂

    叙述极不清晰

    标程过不了我手写的小数据

    ..........

  • 0
    @ 2007-04-06 22:22:34

    宽搜

    中间小的DP

    (还没来得及写,作业太多ing)

  • 0
    @ 2006-11-10 12:20:36

    可惜太长了。。。。。289行。

    注意:

    1.走到end就停止了,不用去管monster!

    2.怪物在走出来之前,不会再掉进去

    。。。。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2006-10-13 20:11:41

    我写了半天的位运算去压缩状态,结果根本不需要,640K判重足矣

  • 0
    @ 2006-02-13 08:36:08

    唯一的想法:

    为何当初我的手机没选M55......

  • 0
    @ 2006-01-23 23:15:00

    宽搜+判重

    看不懂题或者不会的可以去http://spaces.msn.com/members/mrroach/

  • -1
    @ 2017-11-26 15:33:09

    好难啊!同意的赞我!!!

  • -1
    @ 2013-10-24 10:03:27

    呼...花了2小时终于打完了..
    感谢前人们血的教训..

  • -1
    @ 2012-07-10 10:33:20

    被那猥琐的“3秒”搞死了

  • -1
    @ 2009-11-10 10:53:51

    艰难AC了

    终于明白游戏有多么难写- -

    一年前做过,没A

    今天数学课上来了兴致

    翘掉语文课来写这道..

    照来以前写的程序还改了一节多课.

  • -1
    @ 2009-11-04 22:56:45

    为什么WA on test 2 & 7 ?

  • -1
    @ 2009-11-01 21:08:57

    细节太多 描述太...

    AC是因为玩了一下游戏..

信息

ID
1044
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
411
已通过
111
通过率
27%
被复制
8
上传者