QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#299843#1493. Push a BoxXttttr26.666667 92ms59156kbC++142.6kb2024-01-07 11:39:122024-01-07 11:39:13

Judging History

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

  • [2024-01-07 11:39:13]
  • 评测
  • 测评结果:26.666667
  • 用时:92ms
  • 内存:59156kb
  • [2024-01-07 11:39:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1551,M=N*N;
int n,m,Q,S,T,nm;
char s[M];
int dir[4];
bool f[M][4];
inline int id(int x,int y){return x*(m+1)+y;}
int dfn[M],st[M],tp,low[M],cntdfn,scc,fa[M<<1];
inline void tarjan(int x,int lst){
    dfn[x]=low[x]=++cntdfn;
    st[++tp]=x;
    for(int i=0;i<4;i++)if(i^lst){
        int y=x+dir[i];
        if(s[y]!='.')continue;
        if(!dfn[y]){
            tarjan(y,i^1);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                scc++;
                fa[nm+scc]=x;
                while(st[tp]!=x){
                    fa[st[tp]]=nm+scc;
                    tp--;
                }
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
inline bool reach(int x,int y){return fa[x]==fa[y]||fa[fa[x]]==y||fa[fa[y]]==x;}
namespace step1{
    bool vis[M];
    inline void solve(){
        queue<int>q;
        vis[S]=vis[T]=1;
        q.push(S);
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int y=x+dir[i];
                if(s[y]=='.'&&!vis[y])q.push(y),vis[y]=1;
            }
        }
    }
}
inline void solve(){
    queue<pair<int,int> >q;
    for(int i=0;i<4;i++){
        int x=T+dir[i^1];
        if(!step1::vis[x])continue;
        f[T][i]=1;
        q.push({T,i});
    }
    while(!q.empty()){
        int x=q.front().first,d=q.front().second;
        q.pop();
        int y=x+dir[d];
        if(s[y]=='.'&&!f[y][d]){
            f[y][d]=1;
            q.push({y,d});
        }
        int lst=x+dir[d^1];
        for(int i=0;i<4;i++)if(!f[x][i]){
            int y=x+dir[i^1];
            if(s[y]=='.'&&reach(lst,y)){
                f[x][i]=1;
                q.push({x,i});
            }
        }
    }
}
inline bool solve(int x){
    if(x==T)return 1;
    for(int i=0;i<4;i++)if(f[x][i])return 1;
    return 0;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q;
    nm=(n+1)*(m+1);
    dir[0]=-m-1,dir[1]=m+1,dir[2]=-1,dir[3]=1;
    for(int i=1;i<=n;i++){
        cin>>(s+i*(m+1)+1);
        for(int j=i*(m+1)+1;j<=i*(m+1)+m;j++){
            if(s[j]=='A')S=j,s[j]='.';
            else if(s[j]=='B')T=j,s[j]='.';
        }
    }
    tarjan(S,-1);
    step1::solve();
    solve();
    // for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<solve(id(i,j))<<" \n"[j==m];
    while(Q--){
        int x,y;
        cin>>x>>y;
        if(solve(id(x,y)))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
/*
5 5 1
.....
.###.
.#.#.
A.B..
##.##
1 1
*/

详细

Test #1:

score: 6.66667
Accepted
time: 2ms
memory: 11768kb

input:

5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3

output:

NO
YES
NO
NO

result:

ok 4 lines

Test #2:

score: 6.66667
Accepted
time: 2ms
memory: 11660kb

input:

5 5 16
.....
.###.
.#.#.
A.B..
##.##
1 1
1 2
1 3
1 4
1 5
2 1
2 5
3 1
3 3
3 5
4 1
4 2
4 3
4 4
4 5
5 3

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
NO

result:

ok 16 lines

Test #3:

score: 6.66667
Accepted
time: 1ms
memory: 9652kb

input:

5 5 15
...##
A.###
.#...
##..B
##...
1 1
1 2
1 3
2 1
2 2
3 1
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO

result:

ok 15 lines

Test #4:

score: 6.66667
Accepted
time: 0ms
memory: 11780kb

input:

41 46 100
..#.....##.#...............#.#.#...#..........
.#...###.###.#######.#.#.#####.#.#.#..##.#.#.#
.......#...#.............#...........#.#.#.#..
.#.#.#.#####.#.#.###.#.#.#.#.###.#.#.#.#.#.#.#
.#.......#.#.............#...............#.#..
####.###.#..##.#.#.###.#.###.#.#.#####.#.#.###
.#...#.#...

output:

YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
YES
YES
N...

result:

ok 100 lines

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 11896kb

input:

24 31 100
.#.#.#.#.......#.............#.
.###.#.#.#.#####.#.#.#.#.###.#.
.#...#.....#.#.A...............
.#.###.#.###.#.#.#.###.########
...#.#.....#...#.........#.....
.#####.#.###.#.#.###...#.###.#.
......##.#.....#.#.......#.....
..####.#.#.#####.###.#.#.######
...#.........#.#.#...#...#...#.
.#...

output:

NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
YES
NO
YES...

result:

wrong answer 26th lines differ - expected: 'YES', found: 'NO'

Test #6:

score: 0
Wrong Answer
time: 75ms
memory: 54800kb

input:

1500 1500 50000
.....#...#.........#...#...#.#.................#....#....#...#...#...................#.#.....#.#.#...........#.#...#.........#.........#.#...#.....#.............#.#...#.....#.....#...#.#...........#..#........#...#...#...#.....#.........#.....#.#.#.....#.........##......#.#.......#.#...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 8th lines differ - expected: 'YES', found: 'NO'

Test #7:

score: 0
Wrong Answer
time: 78ms
memory: 55584kb

input:

1500 1500 50000
...................#.......#.#.....#...#.#...#.................#.#..#................#.#.....#...#.....##............#.#.#.....#.......#.......#...#.........#.#...#.........#.........#...........#...#.................#.#.......#........#..........#...#.......#.............#.............

output:

NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

wrong answer 2nd lines differ - expected: 'YES', found: 'NO'

Test #8:

score: 0
Wrong Answer
time: 77ms
memory: 58536kb

input:

1500 1500 50000
.....#.........#.....#.#...###...........#...........#.............#.........#.#.#.............................#.#.......#...#.#.....#......#...........##.......##........#.#.#...#................##.#.......#.......................#.#.........#.........#.......#.....##..#.#...#.........

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 18th lines differ - expected: 'YES', found: 'NO'

Test #9:

score: 0
Wrong Answer
time: 91ms
memory: 57784kb

input:

1500 1500 50000
...#.#.....#.#...........#...#...#.#...#.......#...#...................................#..#..#.#.......#.....#.....#.........#.......#.......#.#.........#...#.....#.#.....#.....#.......#.......#.........#.....#.###.............#...#.....#...#...#.....#.........#.#...#...........#.......

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

wrong answer 3rd lines differ - expected: 'YES', found: 'NO'

Test #10:

score: 0
Wrong Answer
time: 80ms
memory: 59156kb

input:

1500 1500 50000
.....#...#.......#....##...........#.#...#.....#..#........#.#.#.##....##..#.#.............#.#......##.#...............#.#.#...#.#.#.#...#.#...#.........#.....#.......#.......###...##........#...#.#.#.....#.#.#.#.#...#.................#.#.............#.###...#.......#...#.#...#.#.......

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 5th lines differ - expected: 'YES', found: 'NO'

Test #11:

score: 0
Wrong Answer
time: 75ms
memory: 56648kb

input:

1500 1500 50000
.#...#...........#...............#...#.........#...............#.......#.#.........................#...........#.#.......#..............##.....#...#.#.....#...#.#.#...#.#...#.....#.#.#...............#...........#.#..#....#.............#...#...#.....#.....#...............#.....#.........

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

wrong answer 5th lines differ - expected: 'YES', found: 'NO'

Test #12:

score: 0
Wrong Answer
time: 92ms
memory: 57000kb

input:

1500 1500 50000
.#.....#...#.#.#...#...#.#.#...#.#....#....#.#.....#.................#.....#...#.#.......#...#..##.....#.....#...#.#...............#.#...#.#...#.....................#...#.....#.#.....#.....#.#.#.....#..........##..#..#.........#.#..##...#.....#...#...#.................#...#.#......#....

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 12th lines differ - expected: 'YES', found: 'NO'

Test #13:

score: 0
Wrong Answer
time: 80ms
memory: 56776kb

input:

1500 1500 50000
...........#...#.#.#.......#...#.....#...#.....#.#.....................................#.#.#..............##.#.............##....#.#.................#.........#..#............#.......#.....##....#...#.....#.#...........#.........#...#.#.....#.#.......#.#.......#...........#...#.#.......

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 4th lines differ - expected: 'YES', found: 'NO'

Test #14:

score: 0
Wrong Answer
time: 84ms
memory: 56652kb

input:

1500 1500 50000
.........#...#...........#.....#.#...#.............#.#.#...#.........#.............#.#...#.#...#.....#.....#.........#...#.#...#...#...........#.....#.....#.#...#...#....#....#.#.#...........#.....#...............#.....#...#...#.#......#........#...#.....#.......#.#.....#...#.#.........

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 3rd lines differ - expected: 'YES', found: 'NO'

Test #15:

score: 0
Wrong Answer
time: 76ms
memory: 56128kb

input:

1500 1500 50000
............##.......#.....#.....#...#...#...#.#.#.#.........#.#.......#.....#.#...#...#.......#.....#.#...........#...#.#.......#...#...#.#...#.....#...#...#.....#......##.#.....#.#...............##....##..#...#...#...........#.......#.....#................#...#....#.#.......#..#..#...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 2nd lines differ - expected: 'YES', found: 'NO'