QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#766256#7733. Cool, It’s Yesterday Four Times MoreDLYdly1105TL 13ms14108kbC++143.1kb2024-11-20 16:45:352024-11-20 16:45:42

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 16:45:42]
  • 评测
  • 测评结果:TL
  • 用时:13ms
  • 内存:14108kb
  • [2024-11-20 16:45:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char s[N][N];
int T,n,m,tot,id[N][N],tot2,id2[N<<1][N<<1];
int fx[10][10],vis[N][N],ok[N][N<<2],ok2[N<<2];
int ans;
queue<pair<int,int>>q;
void bfs(int qx,int qy)
{
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)vis[i][j]=0;
    q.push(make_pair(qx,qy));
    vis[qx][qy]=1;
    ok[id[qx][qy]][id2[n][m]]=1;
    ok2[id2[n][m]]=1;
    while(!q.empty())        
    {
        int x=q.front().first,y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+fx[i][0],ny=y+fx[i][1];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&s[nx][ny]=='.'&&!vis[nx][ny])
            {
                ok[id[qx][qy]][id2[nx-qx+n][ny-qy+m]]=1;
                ok2[id2[nx-qx+n][ny-qy+m]]=1;
                vis[nx][ny]=1;
                q.push(make_pair(nx,ny));
            }
        }
    }
    return;
}
bitset<N>b[N],aa,bb;
void solve()
{
    for(int x=1;x<=n;x++)for(int y=1;y<=m;y++)
    {
        if(s[x][y]!='.')continue;
        b[id[x][y]]=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        {
            b[id[x][y]][(i-1)*m+j]=ok[id[x][y]][id2[i-x+n][j-y+m]];
        }
    }
    int fl=1,fl2;
    b[0]=1;
    for(int i=1;i<=n*m;i++)b[0][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]!='.')continue;
            fl2=1;
            for(int x=1;x<=n;x++)
            {
                for(int y=1;y<=m;y++)
                {
                    if(x==i&&j==y)continue;
                    if(s[x][y]!='.')continue;
                    fl=0;
                    for(int r=1+x-i;r<=n+x-i;r++)
                    {
                        int ll=max(1,1+y-j),rr=min(m,m+y-j),t=r-(x-i);
                        aa=((b[id[i][j]]>>((t-1)*m+1))&(b[0]>>(n*m-m+1)));
                        if(r<1||r>n)bb=0;
                        else bb=(((b[id[x][y]]>>((r-1)*m+ll))&(b[0]>>(n*m-(rr-ll))))<<(m-rr));
                        if((aa&bb)!=aa)
                        {
                            fl=1;
                            break;
                        }
                    }
                    if(!fl){fl2=0;break;}
                }
                if(!fl2)break;
            }
            if(fl2)ans++;
        }
    }
    return;
}
int main()
{
    // freopen("kangaroo.in","r",stdin);
    // freopen("kangaroo.out","w",stdout);
    fx[0][0]=0,fx[0][1]=-1;
    fx[1][0]=0,fx[1][1]=1;
    fx[2][0]=-1,fx[2][1]=0;
    fx[3][0]=1,fx[3][1]=0;
    scanf("%d",&T);
    while(T--)
    {
        tot=tot2=ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=2*n-1;i++)for(int j=1;j<=2*m-1;j++)id2[i][j]=++tot2;
        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s[i][j]=='.')id[i][j]=++tot;
        for(int i=1;i<=tot;i++)for(int j=1;j<=tot2;j++)ok[i][j]=0;
        for(int i=1;i<=tot2;i++)ok2[i]=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s[i][j]=='.')bfs(i,j);
        solve();
        printf("%d\n",ans);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10056kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 4ms
memory: 12336kb

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
3
0
0
1
0
7
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
7
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
5
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
4
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

ok 200 lines

Test #3:

score: 0
Accepted
time: 13ms
memory: 14108kb

input:

50
10 9
OOOO.O...
O...O.OOO
.....O...
..OO..O.O
...O..O.O
..OOO..O.
..OOO...O
.OO.O..OO
.O.O.OO..
.O..O.O.O
10 10
.O.OOO.OO.
...OOOOOOO
...O.O..O.
.O.O..O...
.O.O.OO..O
..OO.O..OO
O....O..OO
OO...OOOOO
OO.OO.O..O
.O.O.OOOOO
10 8
O..OOO.O
O.OOOO..
O..OO.OO
OO..OO..
.OOO..O.
.OO.OO.O
OOO..OO.
..O..OO....

output:

31
40
13
25
40
37
27
29
20
26
25
29
21
29
21
31
32
31
33
34
25
31
18
25
41
28
20
45
20
29
18
21
27
28
35
13
20
17
32
29
28
23
23
23
24
18
28
17
35
24

result:

ok 50 lines

Test #4:

score: -100
Time Limit Exceeded

input:

5
1 1000
....O..OO..O..O..OO...OOO.OOOO.O...O....OOOOO.....OO..OOOO.O..O....OOOO..OO..OOOO......O.O.O..O..OO.OO.OO.O....O.O.O.O.O.OO..O.O.OO..O..OO..O.OOO...O...O.O.O..O....O.OO...O..O...O.OOO..OO.O..O.OO.O.O..OOOO..O.OO.O.O....O.OO.......OOOO....O.O.O.O..OOO.O.OO.OOO..O...O.O.O.O.OO.O.OOOO...O.OO.....

output:


result: