QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#299843 | #1493. Push a Box | Xttttr | 26.666667 | 92ms | 59156kb | C++14 | 2.6kb | 2024-01-07 11:39:12 | 2024-01-07 11:39:13 |
Judging History
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'