AC了2,5,9 其余wa 求助
查看原帖
AC了2,5,9 其余wa 求助
602161
ET_theStarSky楼主2022/12/28 14:18
#include <bits/stdc++.h>

using namespace std;

unsigned long long dper[2][200000]= {0};
int c,r;
int i1,i2,i3,i4,i5,i6,i7,i8,i9;//工具人
int x=0,y=0,now=0;
char shape[100][100]= {0};
int model[20]= {1,3,9,27,81,243,729,2187,2187*3,2187*9,2187*27,2187*81,2187*243,2187*729,2187*2187,2187*2187*3,2187*2187*9,2187*2187*27,2187*2187*81,2187*2187*243};
int get(int key,int bit)
{
    return (key%(model[bit]))/model[bit-1];
}
int ans=0;
int main()
{
    cin>>c>>r;
    if(c<r)
    {

        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                cin>>shape[j][i];
                shape[j][i]=(shape[j][i]=='_')?1:0;
            }
        }
        i1=c;
        c=r;
        r=i1;
    }
    else
    {
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                cin>>shape[i][j];
                shape[i][j]=(shape[i][j]=='_')?1:0;
            }
        }
    }
    //cout<<"init over\n";
    int ex,ey;
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
        {
            if(shape[i][j])
            {
                ex=i;
                ey=j;
            }
            //cout<<int(shape[i][j]);
        }
        //cout<<endl;
    }

    //cout<<ex<<' '<<ey<<endl;
    //cout<<"endfind over\n";
    dper[now][0]=1;
    while( x!=c)
    {
        //cout<<x<<' '<<y<<" st "<<r<<shape[y][x]<<endl;
        for(int i=0; i<(model[r+1]); i++)
        {
            //cout<<dper[now][i]<<' ';
            if(y==r)
            {
                if(get(i,1)==0)
                {
                    dper[!now][i/3]+=dper[now][i];

                }
                continue;
            }
            i4=r-y+1;
            i2=get(i,i4);
            i3=get(i,i4-1);
            if(!shape[y][x])
            {
                if(!(i2||i3))
                {
                    dper[!now][i]+=dper[now][i];
                }
                continue;
            }
            if(i2==0)
            {
                if(i3==0)
                {
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(2*3+2) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(1*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+1) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(2*3+2) + i%model[i4-2]  ]%=20110520;
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(1*3+0) + i%model[i4-2]  ]%=20110520;
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+1) + i%model[i4-2]  ]%=20110520;
                }
                if(i3==1)
                {
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(1*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+2) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(1*3+0) + i%model[i4-2]  ]%=20110520;
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+2) + i%model[i4-2]  ]%=20110520;
                }
                if(i3==2)
                {
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    if(x==ex and y==ey)ans+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(2*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+0) + i%model[i4-2]  ]%=20110520;
                    if(x==ex and y==ey)ans%=20110520;
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(2*3+0) + i%model[i4-2]  ]%=20110520;
                }
            }
            if(i2==1)
            {
                if(i3==0)
                {
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(2*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+1) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(2*3+0) + i%model[i4-2]  ]%=20110520;
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+1) + i%model[i4-2]  ]%=20110520;
                }
                if(i3==1)
                {
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    if(x==ex and y==ey)ans+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+0) + i%model[i4-2]  ]%=20110520;
                    if(x==ex and y==ey)ans%=20110520;
                }
            }
            if(i2==2)
            {
                if(i3==0)
                {
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+2) + i%model[i4-2]  ]+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+0) + i%model[i4-2]  ]+=dper[now][i];
                    if(x==ex and y==ey)ans+=dper[now][i];
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+2) + i%model[i4-2]  ]%=20110520;
                    dper[!now][  (i/model[i4])*model[i4] + model[i4-2]*(0*3+0) + i%model[i4-2]  ]%=20110520;
                    if(x==ex and y==ey)ans%=20110520;
                }
            }
        }
        //cout<<endl;

        memset(dper[now],0,800000);
        //if(x==ex and y==ey)break;
        if(y==r)
        {
            y=0;
            x++;
            now=!now;
        }
        else
        {
            y++;
            now=!now;
        }
    }
    cout<<dper[now][0];
}
2022/12/28 14:18
加载中...