QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72969#2898. Diagonalscodingsword#TL 7019ms339060kbJava114.5kb2023-01-21 05:23:032023-01-21 05:23:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-21 05:23:04]
  • 评测
  • 测评结果:TL
  • 用时:7019ms
  • 内存:339060kb
  • [2023-01-21 05:23:03]
  • 提交

answer

import java.util.*;

public class c {
    static int n;
    static char[][] input;
    static char[][] answer;
    
    static int countIngoing(int i, int j) {
        int result = 0;
        if (i < n && j < n && answer[i][j] == '\\') result += 1;
        if (i > 0 && j < n && answer[i - 1][j] == '/') result += 1;
        if (i < n && j > 0 && answer[i][j - 1] == '/') result += 1;
        if (i > 0 && j > 0 && answer[i - 1][j - 1] == '\\') result += 1;

        return result;
    }

    static int countPerpendicular(int i, int j) {
        int result = 0;
        if (i < n && j < n && answer[i][j] == '/') result += 1;
        if (i > 0 && j < n && answer[i - 1][j] == '\\') result += 1;
        if (i < n && j > 0 && answer[i][j - 1] == '\\') result += 1;
        if (i > 0 && j > 0 && answer[i - 1][j - 1] == '/') result += 1;

        return result;
    }

    static int countUnknown(int i, int j) {
        int result = 0;
        if (i < n && j < n && answer[i][j] == 0) result += 1;
        if (i > 0 && j < n && answer[i - 1][j] == 0) result += 1;
        if (i < n && j > 0 && answer[i][j - 1] == 0) result += 1;
        if (i > 0 && j > 0 && answer[i - 1][j - 1] == 0) result += 1;

        return result;
    }

    static boolean verify() {
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (input[i][j] == '+') continue;
                int expected = input[i][j] - '0';
                int ingoing = countIngoing(i, j);
                int perpen = countPerpendicular(i, j);
                int unknown = countUnknown(i, j);
                if (ingoing > expected) return false;
                if (ingoing + unknown < expected) return false;
            }
        }

        ArrayDeque<Integer> iq = new ArrayDeque<>();
        ArrayDeque<Integer> jq = new ArrayDeque<>();
        boolean[][] visited = new boolean[n + 1][n + 1];
        int[][] ipar = new int[n + 1][n + 1];
        int[][] jpar = new int[n + 1][n + 1];
        for (int[] arr : ipar) Arrays.fill(arr, -1);
        for (int[] arr : jpar) Arrays.fill(arr, -1);
        for (int u = 0; u <= n; ++u) {
            for (int v = 0; v <= n; ++v) {
                if (visited[u][v]) continue;
                iq.add(u);
                jq.add(v);
                visited[u][v] = true;
                while (!iq.isEmpty()) {
                    int i = iq.poll();
                    int j = jq.poll();
                    ArrayList<Integer> ni = new ArrayList<>();
                    ArrayList<Integer> nj = new ArrayList<>();
                    if (i < n && j < n && answer[i][j] == '\\') { ni.add(i + 1); nj.add(j + 1); }
                    if (i > 0 && j < n && answer[i - 1][j] == '/') { ni.add(i - 1); nj.add(j + 1); }
                    if (i < n && j > 0 && answer[i][j - 1] == '/') { ni.add(i + 1); nj.add(j - 1); }
                    if (i > 0 && j > 0 && answer[i - 1][j - 1] == '\\') { ni.add(i - 1); nj.add(j - 1); }
                    for (int index = 0; index < ni.size(); ++index) {
                        int ci = ni.get(index);
                        int cj = nj.get(index);
                        if (visited[ci][cj]) {
                            if (ipar[i][j] == ci && jpar[i][j] == cj) {
                                continue;
                            }
                            return false;
                        }
                        ipar[ci][cj] = i;
                        jpar[ci][cj] = j;
                        visited[ci][cj] = true;
                        iq.add(ci);
                        jq.add(cj);
                    }
                }
            }
        }

        return true;
    }

    static boolean solve(int i, int j) {
        if (!verify()) {
            return false;
        }
        
        if (i == n) {
            return true;
        }

        int ni = i, nj = j + 1;
        if (nj == n) {
            ni += 1;
            nj = 0;
        }

        answer[i][j] = '\\';
        if (solve(ni, nj)) return true;

        answer[i][j] = '/';
        if (solve(ni, nj)) return true;

        answer[i][j] = 0;
        return false;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        scan.nextLine();
        answer = new char[n][n];
        input = new char[n + 1][];
        for (int i = 0; i <= n; ++i) {
            input[i] = scan.nextLine().toCharArray();
        }

        solve(0, 0);

        for (char[] arr : answer) {
            System.out.println(String.valueOf(arr));
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 303ms
memory: 75600kb

input:

8
+11+111++
1++++1++0
1++2++3++
+1+2+1+3+
+213+++++
12+232+++
222+++22+
+++3+3+++
+211+121+

output:

////////
/\\/\//\
/\\///\\
//\/\//\
///////\
////\\\\
\\\/\///
\///\\//

result:

ok 8 lines

Test #2:

score: 0
Accepted
time: 295ms
memory: 74388kb

input:

8
++++++11+
+13+13++1
++21+21++
+11+2222+
+2++3++21
+11+1+2+1
+++322+1+
11+1+1+11
+1++1++++

output:

/\/\\///
\\\\//\/
/\\////\
\\/////\
//\/\//\
\//////\
/\/\\\//
//\\\/\/

result:

ok 8 lines

Test #3:

score: 0
Accepted
time: 188ms
memory: 61312kb

input:

8
++1+++2++
12++23++2
0222322++
+3+11+3+1
++++++++1
+213+2++0
+1+3++22+
2++22+4++
+1+++1+++

output:

\\\\\/\\
\\\\\\\/
////\\\/
/\\///\/
/\\//\\/
/\///\/\
///\/\/\
\\/\//\\

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 105ms
memory: 53940kb

input:

5
+1+2++
1++11+
+3+2++
02+++1
++3+1+
+1+++1

output:

\\/\\
\/\\/
\\\\\
////\
//\\\

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 138ms
memory: 54228kb

input:

5
+++21+
11+2++
1++2++
++32+1
+3++3+
++0+++

output:

\\/\\
\//\/
\\/\/
\//\/
//\\\

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 137ms
memory: 57728kb

input:

5
++1+++
12+++1
+2121+
+2+22+
+323++
++++1+

output:

////\
////\
\\///
\\///
/\/\\

result:

ok 5 lines

Test #7:

score: 0
Accepted
time: 5179ms
memory: 325436kb

input:

8
+++++++++
++4+++22+
+3+++3+3+
++++2+3++
++1++++21
++21++3++
+2+++++21
+4+1+2+11
++++2+1+0

output:

\\//\\\/
\/\\\\\/
//\\/\//
//\\////
\//\\\//
\///////
\//\/\//
/\\\/\\/

result:

ok 8 lines

Test #8:

score: 0
Accepted
time: 104ms
memory: 53800kb

input:

1
01
10

output:

/

result:

ok single line: '/'

Test #9:

score: 0
Accepted
time: 131ms
memory: 54012kb

input:

1
0+
++

output:

/

result:

ok single line: '/'

Test #10:

score: 0
Accepted
time: 102ms
memory: 54864kb

input:

1
10
01

output:

\

result:

ok single line: '\'

Test #11:

score: 0
Accepted
time: 115ms
memory: 53904kb

input:

1
1+
++

output:

\

result:

ok single line: '\'

Test #12:

score: 0
Accepted
time: 103ms
memory: 55928kb

input:

1
+0
++

output:

\

result:

ok single line: '\'

Test #13:

score: 0
Accepted
time: 102ms
memory: 54296kb

input:

1
+1
++

output:

/

result:

ok single line: '/'

Test #14:

score: 0
Accepted
time: 115ms
memory: 53932kb

input:

1
++
0+

output:

\

result:

ok single line: '\'

Test #15:

score: 0
Accepted
time: 118ms
memory: 56184kb

input:

1
++
1+

output:

/

result:

ok single line: '/'

Test #16:

score: 0
Accepted
time: 97ms
memory: 53908kb

input:

1
++
+0

output:

/

result:

ok single line: '/'

Test #17:

score: 0
Accepted
time: 96ms
memory: 54068kb

input:

1
++
+1

output:

\

result:

ok single line: '\'

Test #18:

score: 0
Accepted
time: 285ms
memory: 77536kb

input:

8
+++++++++
+1+2+32+1
++32++4++
+2+4++++1
+3+++++11
++21++3+0
+2++23+++
++1++++1+
+110+0+10

output:

/\\/\\//
\\\//\//
\/\///\/
\//\\///
///\\\\/
\\\\\/\\
//\////\
///\/\//

result:

ok 8 lines

Test #19:

score: 0
Accepted
time: 310ms
memory: 83888kb

input:

8
+++++++++
+3+2+2+20
+2+4+3+++
++1++2++1
+3++2+++1
+++21+2+2
++2++24++
+2+3++++1
+2+112+2+

output:

\/\/\///
\\\/\/\\
///\\\\\
\\//\\/\
/\//\\/\
//\\\\//
\/\///\/
\/\\\/\/

result:

ok 8 lines

Test #20:

score: 0
Accepted
time: 406ms
memory: 100508kb

input:

7
++++++++
+23131+1
+11+1+2+
++2++1+1
+3++3+++
++22222+
+3+3222+
++2+1+2+

output:

/////\/
//\/\\/
\////\/
\//\///
\\\\\\/
\\\\\\/
/\/\\\/

result:

ok 7 lines

Test #21:

score: 0
Accepted
time: 316ms
memory: 80424kb

input:

7
++++++++
+21221+0
+++1+3++
+3+2++21
+233++2+
+++++2+1
+21+2++1
+++12+2+

output:

/////\/
\\////\
\/\//\\
\\\//\\
//\\///
//\\///
\\\\/\/

result:

ok 7 lines

Test #22:

score: 0
Accepted
time: 538ms
memory: 114128kb

input:

8
+++++++++
+2+233+21
+24++2+21
++++++1+1
+3++21+22
+23+++3++
+++3+++11
+21++21+0
+1110++1+

output:

\\\\\/\\
\\//\\\\
//\///\\
\////\\\
\\\\\\//
//\/////
//\\//\/
////\\\\

result:

ok 8 lines

Test #23:

score: 0
Accepted
time: 284ms
memory: 75072kb

input:

8
+++++++++
+11+1+4+0
++2++3+++
+131+++1+
++1+3+320
+2+2+11++
+23+1+2++
+31++1++1
+0+112+0+

output:

//\/\\//
\//\\/\\
///\///\
\/\\////
//////\\
////\//\
//\////\
/\\\\//\

result:

ok 8 lines

Test #24:

score: 0
Accepted
time: 195ms
memory: 68892kb

input:

7
++++++++
+24++1+1
++++2+3+
++23+231
+3++2+++
+33+121+
++++++2+
++0+11+1

output:

\\///\/
//\/\\/
\\\/\\\
\/////\
\\////\
/\\\///
//\\\\\

result:

ok 7 lines

Test #25:

score: 0
Accepted
time: 272ms
memory: 75028kb

input:

7
++++++++
+232+2+1
+++2++3+
+322+2++
++24+1+2
++++++2+
+2++2+4+
+0+10+++

output:

\\\//\/
//\//\/
\\\//\\
/\\//\\
///\\\/
/\//\\/
/\//\/\

result:

ok 7 lines

Test #26:

score: 0
Accepted
time: 477ms
memory: 122560kb

input:

8
+++++++++
++3+3+3++
+3+3+3+3+
++3+++3++
+3+++++2+
++3+++32+
+3+3+3+31
++3+2+3++
+++++++++

output:

\\\\\\//
\/\/\///
\\\\\\/\
\/\\/\\\
\\\/\\\\
\/\\\/\\
///\///\
//\\//\\

result:

ok 8 lines

Test #27:

score: 0
Accepted
time: 124ms
memory: 53936kb

input:

3
++++
+1+1
+31+
+0+0

output:

/\/
///
/\/

result:

ok 3 lines

Test #28:

score: 0
Accepted
time: 121ms
memory: 55156kb

input:

4
+++++
+3++2
++3++
+3+3+
++2+0

output:

\//\
\\//
\\\/
/\//

result:

ok 4 lines

Test #29:

score: 0
Accepted
time: 230ms
memory: 69688kb

input:

7
++++++++
+3+3+3++
++3++23+
+3+++321
++3+++3+
+3+++3++
++3+3+3+
+++1++++

output:

\\\/\//
/\//\\/
///\\\\
/\///\\
///\//\
/\/\/\\
//////\

result:

ok 7 lines

Test #30:

score: 0
Accepted
time: 3338ms
memory: 269888kb

input:

8
+++++++++
+3+24+++2
++4+++2++
+++++21+1
+3+3++2++
++3+2++2+
+++3+++3+
++++3+3+2
+2+2+2+2+

output:

\\\\//\\
/\//\/\/
//\///\/
\\\/////
/\\\\\\/
//\//\\/
\/\\\\\\
\/\/\/\/

result:

ok 8 lines

Test #31:

score: 0
Accepted
time: 7019ms
memory: 339060kb

input:

8
+++++++++
+22+2+2+1
+32+2+2+1
++2+2+1+2
++2+3++2+
+22++2+3+
++3++22+1
+3+3+++3+
++2+110++

output:

\\/\//\\
\\/\//\\
/\/\//\\
\\/\/\\/
\\/\\\\/
\\//////
\\\/\\\/
/\////\\

result:

ok 8 lines

Test #32:

score: 0
Accepted
time: 774ms
memory: 144576kb

input:

8
+++++++++
+33++3+3+
+++++33++
++3+++++1
+3+3+++2+
++3+1+32+
+++2+3+31
+1+++23++
+11+1+1++

output:

\\//\///
/\\\\\/\
\\///\\\
\\\//\\\
/\//\\//
/\\\\\\\
/\///\/\
/////\\\

result:

ok 8 lines

Test #33:

score: 0
Accepted
time: 3299ms
memory: 227964kb

input:

8
+++++++++
+33++23+0
++++2++1+
++3++3+30
+3+22+2++
++3++22++
+3++++3+0
+3+223+2+
++++++2+0

output:

\\//\\//
/\\////\
\\/\\\//
\////\/\
\\\\\\/\
\/\\\\//
\\\\\\\\
/\///\//

result:

ok 8 lines

Test #34:

score: 0
Accepted
time: 5484ms
memory: 282412kb

input:

8
+++++++++
++3++2+20
+3+3+1+++
++2+3+++2
+++++3+++
+2+2++3++
+1+1+3++1
++3++33++
+1+1++++0

output:

\\///\//
\\\\/\\\
/\/\//\\
/\/\\///
/\/\\\//
/\/\\///
\\//\\//
/////\\/

result:

ok 8 lines

Test #35:

score: 0
Accepted
time: 482ms
memory: 132648kb

input:

8
+++++++++
+3+1+1+22
++22222++
+2+++++22
++2+2+2++
+++2+3++2
+2++2+2++
+4+++3+22
+++11++++

output:

\//\/\\\
////////
\\\\\\\\
////////
\\\\\//\
\///////
\//\\\\\
/\///\//

result:

ok 8 lines

Test #36:

score: -100
Time Limit Exceeded

input:

8
+++++++++
+2+2+2+2+
+2+2+2+2+
+2+2+2+2+
+2+2+2+2+
+2+2+2+2+
+2+2+2+2+
+2+2+2+2+
+0+0+0+0+

output:


result: