QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #834464 | #9926. Flipping Paths | MCPlayer542# | WA | 2ms | 2396kb | C++14 | 2.3kb | 2024-12-27 17:47:54 | 2024-12-27 17:47:54 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,l,anc,p[210][410],pc[210];
char s[210][210],ans[810][410];
bool g[210][210];
bool work()
{
for(int i=0;i<n;++i) pc[i]=0;
if(g[0][0]^g[n-1][m-1]) return 0;
for(int i=1;i<n+m-2;++i)
{
for(int j=max(i-m+1,0);j<i&&j<n-1;++j) if(g[0][0]^g[j][i-j])
{
g[j][i-j]^=1;
g[j+1][i-j-1]^=1;
p[j][pc[j]++]=i-j-1;
}
if(g[0][0]^g[min(i,n-1)][i-min(i,n-1)]) return 0;
}
//for(int i=0;i<n;++i){printf("%d: ",i);
//for(int j=0;j<pc[i];++j) printf("%d ",p[i][j]);putchar('\n');}
while(1)
{
pair<int,int> cur(0,0);
for(int i=0;i<n;++i) if(pc[i]&&p[i][pc[i]-1]>=cur.second)
{
--pc[i];
while(cur.first<i)
{
ans[anc][cur.first+cur.second]='D';
ans[anc+1][cur.first+cur.second]='D';
++cur.first;
}
while(cur.second<p[i][pc[i]])
{
ans[anc][cur.first+cur.second]='R';
ans[anc+1][cur.first+cur.second]='R';
++cur.second;
}
ans[anc][cur.first+cur.second]='R';
ans[anc][cur.first+cur.second+1]='D';
ans[anc+1][cur.first+cur.second]='D';
ans[anc+1][cur.first+cur.second+1]='R';
++cur.first,++cur.second;
}
if(cur==make_pair(0,0)) break;
while(cur.first<n-1)
{
ans[anc][cur.first+cur.second]='D';
ans[anc+1][cur.first+cur.second]='D';
++cur.first;
}
while(cur.second<m-1)
{
ans[anc][cur.first+cur.second]='R';
ans[anc+1][cur.first+cur.second]='R';
++cur.second;
}
anc+=2;
}
printf("YES\n");
int tmp=0;
for(int i=0;i<anc;++i)
{
for(int j=0;j<n+m-2;++j) ans[tmp][j]=ans[i][j];
if(tmp&&!strcmp(ans[tmp-1],ans[tmp])) --tmp;
else ans[tmp++][n+m-2]=0;
}
printf("%d\n",tmp);
for(int i=0;i<tmp;++i) printf("%s\n",ans[i]);
return 1;
}
void solve()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
scanf(" %s",s[i]);
for(int j=0;j<m;++j) g[i][j]=s[i][j]=='B';
}
anc=0;
if(work()) return;
anc=1;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j) g[i][j]=s[i][j]=='B';
for(int i=0;i<m;++i)
{
g[0][i]^=1;
ans[0][i]='R';
}
for(int i=1;i<n;++i)
{
g[i][m-1]^=1;
ans[0][m+i-2]='D';
}
if(work()) return;
printf("NO\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--) solve();
return 0;
}
/*
4
3 3
WBB
BWB
BBW
1 5
WWWWW
2 2
BB
BB
4 1
W
B
B
W
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1728kb
input:
4 3 3 WBB BWB BBW 1 5 WWWWW 2 2 BB BB 4 1 W B B W
output:
YES 2 RRDD DDRR YES 0 YES 0 NO
result:
ok ok (4 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 1720kb
input:
323 1 2 BB 1 2 BW 1 2 WB 1 2 WW 2 1 B B 2 1 B W 2 1 W B 2 1 W W 1 3 BBB 1 3 BBW 1 3 BWB 1 3 BWW 1 3 WBB 1 3 WBW 1 3 WWB 1 3 WWW 2 2 BB BB 2 2 BB BW 2 2 BB WB 2 2 BB WW 2 2 BW BB 2 2 BW BW 2 2 BW WB 2 2 BW WW 2 2 WB BB 2 2 WB BW 2 2 WB WB 2 2 WB WW 2 2 WW BB 2 2 WW BW 2 2 WW WB 2 2 WW WW 3 1 B B B 3 ...
output:
YES 0 NO NO YES 0 YES 0 NO NO YES 0 YES 0 NO NO NO NO NO NO YES 0 YES 0 NO YES 1 RD NO YES 1 DR NO YES 2 RD DR NO NO YES 2 RD DR NO YES 1 DR NO YES 1 RD NO YES 0 YES 0 NO NO NO NO NO NO YES 0 YES 0 NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES 0 YES 0 NO NO NO NO NO YES 1 RRD NO NO NO YES 2 RRD RDR ...
result:
ok ok (323 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 1736kb
input:
278 2 4 BWBW WWBB 2 4 BWBW WWBW 2 4 BWBW WWWB 2 4 BWBW WWWW 2 4 BWWB BBBB 2 4 BWWB BBBW 2 4 BWWB BBWB 2 4 BWWB BBWW 2 4 BWWB BWBB 2 4 BWWB BWBW 2 4 BWWB BWWB 2 4 BWWB BWWW 2 4 BWWB WBBB 2 4 BWWB WBBW 2 4 BWWB WBWB 2 4 BWWB WBWW 2 4 BWWB WWBB 2 4 BWWB WWBW 2 4 BWWB WWWB 2 4 BWWB WWWW 2 4 BWWW BBBB 2 ...
output:
NO NO NO NO NO NO YES 3 RRRD RRDR DRRR NO NO NO NO NO NO NO NO NO YES 2 RRDR DRRR NO NO NO YES 1 DRRR NO NO NO NO NO NO NO NO NO NO NO NO NO YES 2 RRRD DRRR NO NO YES 2 RRRD DRRR NO NO NO NO NO NO NO NO NO NO NO NO NO YES 1 DRRR NO NO NO YES 2 RRDR DRRR NO NO NO NO NO NO NO NO NO YES 3 RRRD RRDR DRR...
result:
ok ok (278 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 1732kb
input:
333 3 3 BBW WWB BWB 3 3 BBW WWB BWW 3 3 BBW WWB WBB 3 3 BBW WWB WBW 3 3 BBW WWB WWB 3 3 BBW WWB WWW 3 3 BBW WWW BBB 3 3 BBW WWW BBW 3 3 BBW WWW BWB 3 3 BBW WWW BWW 3 3 BBW WWW WBB 3 3 BBW WWW WBW 3 3 BBW WWW WWB 3 3 BBW WWW WWW 3 3 BWB BBB BBB 3 3 BWB BBB BBW 3 3 BWB BBB BWB 3 3 BWB BBB BWW 3 3 BWB ...
output:
YES 3 RDRD DRDR DDRR NO NO NO NO NO YES 3 RDRD DRRD DDRR NO NO NO NO NO NO NO NO NO YES 3 RRDD RDDR DDRR NO NO NO NO NO YES 3 RRDD RDRD DDRR NO NO NO NO NO NO NO NO NO NO NO NO NO YES 3 RRDD RDDR DRDR NO NO NO NO NO YES 3 RRDD RDRD DRDR NO NO NO YES 2 RDDR DRDR NO NO NO NO NO NO NO NO NO YES 2 RDRD ...
result:
ok ok (333 test cases)
Test #5:
score: 0
Accepted
time: 0ms
memory: 1632kb
input:
266 3 3 WWB WWW WWW 3 3 WWW BBB BBB 3 3 WWW BBB BBW 3 3 WWW BBB BWB 3 3 WWW BBB BWW 3 3 WWW BBB WBB 3 3 WWW BBB WBW 3 3 WWW BBB WWB 3 3 WWW BBB WWW 3 3 WWW BBW BBB 3 3 WWW BBW BBW 3 3 WWW BBW BWB 3 3 WWW BBW BWW 3 3 WWW BBW WBB 3 3 WWW BBW WBW 3 3 WWW BBW WWB 3 3 WWW BBW WWW 3 3 WWW BWB BBB 3 3 WWW ...
output:
NO NO NO NO YES 3 RRDD DRRD DRDR NO NO NO NO NO YES 1 RRDD NO NO NO NO NO NO NO NO NO NO NO NO NO YES 3 RRDD DRRD DDRR NO NO NO NO NO YES 3 RRDD DRDR DDRR NO NO NO YES 2 DRRD DDRR NO NO NO NO NO NO NO NO NO YES 2 DRDR DDRR NO NO NO NO NO NO NO NO NO YES 2 DRRD DRDR NO NO NO NO NO NO NO NO NO YES 0 Y...
result:
ok ok (266 test cases)
Test #6:
score: 0
Accepted
time: 0ms
memory: 1660kb
input:
245 4 2 WW BB WB BW 4 2 WW BB WB WB 4 2 WW BB WB WW 4 2 WW BB WW BB 4 2 WW BB WW BW 4 2 WW BB WW WB 4 2 WW BB WW WW 4 2 WW BW BB BB 4 2 WW BW BB BW 4 2 WW BW BB WB 4 2 WW BW BB WW 4 2 WW BW BW BB 4 2 WW BW BW BW 4 2 WW BW BW WB 4 2 WW BW BW WW 4 2 WW BW WB BB 4 2 WW BW WB BW 4 2 WW BW WB WB 4 2 WW B...
output:
NO NO YES 3 RDDD DRDD DDDR NO YES 3 RDDD DRDD DDRD NO NO NO NO NO YES 3 RDDD DDRD DDDR NO YES 1 RDDD NO NO NO NO NO NO NO NO NO NO NO YES 2 DRDD DDDR NO NO NO NO NO YES 2 DRDD DDRD NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES 2 DDRD DDDR NO NO NO NO NO YES 0 YES 0 NO NO NO NO NO NO NO NO N...
result:
ok ok (245 test cases)
Test #7:
score: 0
Accepted
time: 0ms
memory: 1572kb
input:
200 5 3 BBB BBB WBW BBW BBW 5 3 BBB BBB WBW BBW BWB 5 3 BBB BBB WBW BBW BWW 5 3 BBB BBB WBW BBW WBB 5 3 BBB BBB WBW BBW WBW 5 3 BBB BBB WBW BBW WWB 5 3 BBB BBB WBW BBW WWW 5 3 BBB BBB WBW BWB BBB 5 3 BBB BBB WBW BWB BBW 5 3 BBB BBB WBW BWB BWB 5 3 BBB BBB WBW BWB BWW 5 3 BBB BBB WBW BWB WBB 5 3 BBB ...
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:
ok ok (200 test cases)
Test #8:
score: 0
Accepted
time: 0ms
memory: 1612kb
input:
200 5 4 BWWB WBWW WBWW WBWW WBBW 5 4 BWWB WBWW WBWW WBWW WBWB 5 4 BWWB WBWW WBWW WBWW WBWW 5 4 BWWB WBWW WBWW WBWW WWBB 5 4 BWWB WBWW WBWW WBWW WWBW 5 4 BWWB WBWW WBWW WBWW WWWB 5 4 BWWB WBWW WBWW WBWW WWWW 5 4 BWWB WBWW WBWW WWBB BBBB 5 4 BWWB WBWW WBWW WWBB BBBW 5 4 BWWB WBWW WBWW WWBB BBWB 5 4 BW...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES 4 RRDRDDD DRDRDRD DRDDRDR DDDDRRR NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES 4 RRDRDDD DRDRDRD DRDDRRD DDDDRRR NO NO NO NO NO NO NO NO NO YES 4 RRDRDDD DRDRDRD DRDDDRR DDDDRRR NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok ok (200 test cases)
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 2396kb
input:
5 200 200 WBWWWBWBWWWWBWWWBBBBBBWBWWBWWBBWBWWBWBBBWBBWBBWBWBBWWWWWWBWWWBBWBWBWBWBBWBWWBWWBWBBBWWWBWBBWWBBBBBWWBBBBWWBBWBWWWBBWBWBWWWWBBWBWWBWWWWWBWWBBBBBWBBWBWWWWWBWWWBWBWWBBBBWWBWWWWBWBBWBWBBWWBWWBBWBWBWWBWBWB BBWBBBBBWBWWWWWWWWWWBBWWWWBWWBWWBBBBBWWWBWBWWBBWBBWWBBBBBWWBWBWBWWBWBWBBBBWWWWBWBBBBBWBBB...
output:
YES 700 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...
result:
wrong answer Integer 700 violates the range [0, 400] (test case 1)