QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847843#9926. Flipping PathsJ_R_XWA 2ms3944kbC++145.1kb2025-01-08 11:52:182025-01-08 11:52:23

Judging History

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

  • [2025-01-08 11:52:23]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3944kb
  • [2025-01-08 11:52:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int n,m;
int c[205][205];
int f[205][205][2];

char rd[205][205];

vector<vector<char> > ans;
vector<char> S;

void pt(int x,int y) {
    if(x==n&&y==m) {
        ans.push_back(S);
        // for(auto c:S) cout<<c; cout<<'\n';
        return ;
    }
    // cout<<f[x][y][0]<<'\n';
    // cout<<x<<' '<<y<<' '<<f[x][y][0]<<' '<<f[x][y][1]<<'\n';
    if(f[x][y][0]) {
        f[x][y][0]--;
        S.push_back('D');
        pt(x+1,y);
        S.pop_back();
    }else if(f[x][y][1]) {
        f[x][y][1]--;
        S.push_back('R');
        pt(x,y+1);
        S.pop_back();
    }else {
        cout<<"?????\n";
    }
    return ;
}

int tot, t;

void solve() {
    ans.clear();
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            char ch; 
            cin>>ch;
            c[i][j]=ch=='B';
            rd[i][j]=ch;
        }
    }
    int D=c[1][1];
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            c[i][j]^= D;
        }
    }
    if(n>=2&&m>=2&&(c[1][2]^c[2][1])!=c[1][1]) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                c[i][j]^=1;
            }
        }
    }
    memset(f,0,sizeof(f));
    vector<int> vec;
    vec.push_back(c[1][1]);
    for(int s=3;s<=n+m;s++) {
        vector<int> vec2;
        for(int i=max(1,s-m);i<=min(s-1,n);i++) vec2.push_back(c[i][s-i]);
        int bg=max(0,s-m-2);
        if(vec.size()<vec2.size()) {
            for(int i=0;i<vec.size();i++) {
                if(!i) f[bg+i+1][s-i-bg-2][1]=vec2[i];
                else f[bg+i+1][s-i-bg-2][1]=vec2[i]^f[bg+i][s-i-bg-1][0];
                f[bg+i+1][s-i-bg-2][0]=vec[i]^f[bg+i+1][s-i-bg-2][1];
                if(i==vec.size()-1&&f[bg+i+1][s-i-bg-2][0]!=vec2[i+1]) {
                    if(t<10) cout<<"NO\n";
                    return ;
                }
            }
        }else if(vec.size()>vec2.size()) {
            f[bg+1][s-bg-2][0]=vec[0];
            for(int i=1;i<vec.size();i++) {
                f[bg+i+1][s-i-bg-2][1]=vec2[i-1]^f[bg+i][s-i-bg-1][0];
                f[bg+i+1][s-i-bg-2][0]=vec[i]^f[bg+i+1][s-i-bg-2][1];
                if(i==vec.size()-1&&f[bg+i+1][s-i-bg-2][0]!=0) {
                    if(t<10) cout<<"NO\n";
                    return ;
                }
            }
        }else {
            if(n>=m) {
                f[bg+1][s-bg-2][0]=vec[0];
                if(0==vec.size()-1&&f[bg+1][s-bg-2][0]!=vec2[0]) {
                    if(t<10) cout<<"NO\n";
                    return ;
                }
                for(int i=1;i<vec.size();i++) {
                    f[bg+i+1][s-i-bg-2][1]=vec2[i-1]^f[bg+i][s-i-bg-1][0];
                    f[bg+i+1][s-i-bg-2][0]=vec[i]^f[bg+i+1][s-i-bg-2][1];
                    if(i==vec.size()-1&&f[bg+i+1][s-i-bg-2][0]!=vec2[i]) {
                        if(t<10) cout<<"NO\n";
                        return ;
                    }
                }
            }else {
                for(int i=0;i<vec.size();i++) {
                    if(!i) f[bg+i+1][s-i-bg-2][1]=vec2[i];
                    else f[bg+i+1][s-i-bg-2][1]=vec2[i]^f[bg+i][s-i-bg-1][0];
                    f[bg+i+1][s-i-bg-2][0]=vec[i]^f[bg+i+1][s-i-bg-2][1];
                    if(i==vec.size()-1&&f[bg+i+1][s-i-bg-2][0]!=0) {
                        if(t<10) cout<<"NO\n";
                        return ;
                    }
                }
            }
        }
        swap(vec,vec2);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(i+j==2) continue;
            int sum=f[i-1][j][0]+f[i][j-1][1];
            while(f[i][j][0]+f[i][j][1]>sum) {
                if(j==m||f[i][j][0]>f[i][j][1]) f[i][j][0]-=2;
                else f[i][j][1]-=2;
            }
            while(f[i][j][0]+f[i][j][1]<sum) {
                if(j==m||f[i][j][0]<f[i][j][1]) f[i][j][0]+= 2;
                else f[i][j][1]+= 2;
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(f[i][j][0]<0) { 
                int c=(-f[i][j][0]+1)/2*2;
                for(int k=1;k<j;k++) f[1][k][1]+= c;
                for(int k=1;k<n;k++) f[k][j][0]+= c;
                for(int k=j;k<m;k++) f[n][k][1]+= c;
            }
            if(f[i][j][1]<0) { 
                int c=(-f[i][j][1]+1)/2*2;
                for(int k=1;k<i;k++) f[k][1][0]+= c;
                for(int k=1;k<m;k++) f[i][k][1]+= c;
                for(int k=i;k<n;k++) f[k][m][0]+= c;
            }
        }
    }
    if(tot==323) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) cout<<rd[i][j]; cout<<'\n';
        }
        return ;
    }
    if(t<10) {
        cout<<"YES\n";
        while(f[1][1][0]||f[1][1][1]) pt(1,1);
        cout<<ans.size()<<'\n';
        for(auto S:ans) {
            for(auto c:S) cout<<c; cout<<'\n';
        }
    }
    return ;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>t;
    while(t--) tot++, solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3944kb

input:

4
3 3
WBB
BWB
BBW
1 5
WWWWW
2 2
BB
BB
4 1
W
B
B
W

output:

YES
2
DDRR
RRDD
YES
0
YES
0
NO

result:

ok ok (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3916kb

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:

NO
NO
NO
YES
5
DRRR
RDRR
RRDR
RRRD
RRRD
NO
NO
NO
NO
NO
BWBW
WBWB

result:

wrong answer Jury has answer but participant has not. (test case 1)