QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390900#4681. KeyboardingTWTP_TCTF#AC ✓885ms122136kbC++202.3kb2024-04-16 06:58:412024-04-16 06:58:41

Judging History

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

  • [2024-04-16 06:58:41]
  • 评测
  • 测评结果:AC
  • 用时:885ms
  • 内存:122136kb
  • [2024-04-16 06:58:41]
  • 提交

answer

#include<iostream>
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define rep(i, a, b) for(int i = a ; i < b ; i ++)
#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 55;
int n, m;
char a[N][N];

int dis[10005][N][N];
int nxt[N][N][4];

void preprocess() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            nxt[i][j][0] = j;
            while (a[i][nxt[i][j][0]] == a[i][j] && nxt[i][j][0] < m)nxt[i][j][0]++;

            nxt[i][j][1] = j;
            while (a[i][nxt[i][j][1]] == a[i][j] && nxt[i][j][1] >= 0)nxt[i][j][1]--;


            nxt[i][j][2] = i;
            while (a[nxt[i][j][2]][j] == a[i][j] && nxt[i][j][2] < n)nxt[i][j][2]++;

            nxt[i][j][3] = i;
            while (a[nxt[i][j][3]][j] == a[i][j] && nxt[i][j][3] >= 0)nxt[i][j][3]--;

            if (nxt[i][j][0] == m)nxt[i][j][0] = -1;
            if (nxt[i][j][2] == n)nxt[i][j][2] = -1;

        }
    }
}

void doWork() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    preprocess();

    string s;
    cin >> s;
    s = s + '*';

    queue<vector<int> > q;
    q.push({0, 0, 0});
    memset(dis, -1, sizeof dis);
    while (!q.empty()) {
        int idx = q.front()[0], x = q.front()[1], y = q.front()[2];
        if (idx == s.size()) {
            cout << dis[idx][x][y] + 1;
            return;
        }
        q.pop();
        if (s[idx] == a[x][y] && dis[idx + 1][x][y] == -1) {
            dis[idx + 1][x][y] = dis[idx][x][y] + 1;
            q.push({idx + 1, x, y});
        }
        for (int i = 0; i < 4; i++) {
            if (nxt[x][y][i] != -1) {
                int nxt_x = i < 2 ? x : nxt[x][y][i];
                int nxt_y = i < 2 ? nxt[x][y][i] : y;
                if (dis[idx][nxt_x][nxt_y] == -1) {
                    dis[idx][nxt_x][nxt_y] = dis[idx][x][y] + 1;
                    q.push({idx, nxt_x, nxt_y});
                }
            }
        }

    }
    assert(false);
}

int main() {
//    IO

    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 122008kb

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

score: 0
Accepted
time: 3ms
memory: 121812kb

input:

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

output:

160

result:

ok 1 number(s): "160"

Test #3:

score: 0
Accepted
time: 3ms
memory: 121724kb

input:

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

output:

19

result:

ok 1 number(s): "19"

Test #4:

score: 0
Accepted
time: 0ms
memory: 122096kb

input:

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 15ms
memory: 121784kb

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

score: 0
Accepted
time: 8ms
memory: 121844kb

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 4ms
memory: 121868kb

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: 0
Accepted
time: 7ms
memory: 121836kb

input:

12 11
AAAAAAAAAAA
ABBBBBBBBBA
ABCCCCCCCBA
ABCDDDDDCBA
ABCDEEEDCBA
ABCDEFEDCBA
ABCDEEEDCBA
ABCDDDDDCBA
ABCCCCCCCBA
ABBBBBBBBBA
AAAAAAAAAAA
***********
AAA

output:

5

result:

ok 1 number(s): "5"

Test #9:

score: 0
Accepted
time: 65ms
memory: 121836kb

input:

6 28
AABBCCDDEEFFGGHHIIJJKKLLMNNN
AABBCCDDEEFFGGHHIIJJKKLLMMMN
OOPPQQRRSSTTUUVVWWXXYYZZ00**
OOPPQQRRSSTTUUVVWWXXYYZZ0011
222333444555666777888999--11
222333444555666777888999----
1THE-QUICK-BROWN-FOX-JUMPS-OVER-THE-LAZY-DOG2THE-QUICK-BROWN-FOX-JUMPS-OVER-THE-LAZY-DOG3THE-QUICK-BROWN-FOX-JUMPS-OVER-T...

output:

64174

result:

ok 1 number(s): "64174"

Test #10:

score: 0
Accepted
time: 39ms
memory: 121816kb

input:

30 30
A11111111111111111111111111111
0B1111111111111111111111111111
00C111111111111111111111111111
000D11111111111111111111111111
0000E1111111111111111111111111
00000F111111111111111111111111
000000G11111111111111111111111
0000000H1111111111111111111111
00000000I111111111111111111111
000000000J11111...

output:

590057

result:

ok 1 number(s): "590057"

Test #11:

score: 0
Accepted
time: 40ms
memory: 122084kb

input:

30 30
A11111111111111111111111111111
0B1111111111111111111111111111
00C111111111111111111111111111
000D11111111111111111111111111
0000E1111111111111111111111111
00000F111111111111111111111111
000000G11111111111111111111111
0000000H1111111111111111111111
00000000I111111111111111111111
000000000J11111...

output:

30001

result:

ok 1 number(s): "30001"

Test #12:

score: 0
Accepted
time: 8ms
memory: 122036kb

input:

4 10
QWERTYUIOP
ASDFGHJKL*
ZXCVBNM***
----------
GA-NU-MAAR-LIGGEN-LIEFSTE-IN-DE-TUIN-DE-LEGE-PLEKKEN-IN-HET-HOGE-GRAS-IK-HEB-ALTIJD-GEWILD-DAT-IK-DAT-WAS-EEN-LEGE-PLEK-VOOR-IEMAND-OM-TE-BLIJVEN

output:

676

result:

ok 1 number(s): "676"

Test #13:

score: 0
Accepted
time: 4ms
memory: 121980kb

input:

24 30
QQQWWWEEERRRTTTYYYUUUIIIOOOPPP
QQQWWWEEERRRTTTYYYUUUIIIOOOPPP
QQQWWWEEERRRTTTYYYUUUIIIOOOPPP
QQQWWWEEERRRTTTYYYUUUIIIOOOPPP
QQQWWWEEERRRTTTYYYUUUIIIOOOPPP
QQQWWWEEERRRTTTYYYUUUIIIOOOPPP
AAASSSDDDFFFGGGHHHJJJKKKLLL***
AAASSSDDDFFFGGGHHHJJJKKKLLL***
AAASSSDDDFFFGGGHHHJJJKKKLLL***
AAASSSDDDFFFGGG...

output:

2236

result:

ok 1 number(s): "2236"

Test #14:

score: 0
Accepted
time: 600ms
memory: 121936kb

input:

50 50
*0000000000000000000000000000000000000000000000000
00011001100110011001100110011001100110011001100111
01001100110011001100110011001100110011001100110011
01100110011001100110011001100110011001100110011001
00110011001100110011001100110011001100110011001101
000110011001100110011001100110011001100...

output:

20003

result:

ok 1 number(s): "20003"

Test #15:

score: 0
Accepted
time: 675ms
memory: 122000kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA
ABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABA
ABABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

20001

result:

ok 1 number(s): "20001"

Test #16:

score: 0
Accepted
time: 58ms
memory: 122128kb

input:

50 50
0*************************************************
--************************************************
---***********************************************
----**********************************************
-----*********************************************
------*********************************...

output:

979905

result:

ok 1 number(s): "979905"

Test #17:

score: 0
Accepted
time: 839ms
memory: 122104kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
*AAABABBBABAAABABBBABAAABABBBABAAABABBBABAAABABBBA
BAAABABBBABAAABABBBABAAABABBBABAAABABBBABAAABAB0BA
BAAABABBBABAAABABBBABAAABABBBABAAABABBBABAAABABBBA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1650040

result:

ok 1 number(s): "1650040"

Test #18:

score: 0
Accepted
time: 885ms
memory: 122136kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
4AAABABBBABAAABABBBABABABABABABAAABABBBABAAABABBBA
BAAABABBBABAAABABBBABABABABABABAAABABBBABAAABAB0BA
BAAABABBBABAAABABBBABABABABABABAAABABBBABAAABABBBA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1810204

result:

ok 1 number(s): "1810204"

Test #19:

score: 0
Accepted
time: 818ms
memory: 121872kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBAAABABBBABAAABABBBABAABABABABAAABABBBABAAABABBBA
0BAAABABBBABAAABABBBABAABABABABAAABABBBABAAABAB4BA
BBAAABABBBABAAABABBBABAABABABABAAABABBBABAAABABBBA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

3270317

result:

ok 1 number(s): "3270317"