QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#383967#4681. KeyboardingEnergy_is_not_over#AC ✓424ms109720kbC++172.5kb2024-04-09 19:22:242024-04-09 19:22:24

Judging History

This is the latest submission verdict.

  • [2024-04-09 19:22:24]
  • Judged
  • Verdict: AC
  • Time: 424ms
  • Memory: 109720kb
  • [2024-04-09 19:22:24]
  • Submitted

answer

//
// Stvoreno ENERGom o 09.04.24. 13:11:02
//

#include<bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define MP make_pair
#define pb push_back
#define PB push_back
#define F first
#define fir first
#define S second
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy
#define DEBUG for (int ____DEBUG=1;____DEBUG;____DEBUG=0)

template<class ...Ts>
auto &PRNT(Ts ...ts) { return ((cerr << ts << " "), ...); }

#define LOG(...) PRNT(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
#else
#define DEBUG while(0)
#define LOG(...)
#endif

const int max_n = 52, inf = 1000111222;
const int max_len = 10011;
const int max_v = max_n * max_n;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, m, dist[max_v][max_len];
string a[max_n], s, t;
vector<int> g[max_v];

bool is_in(int x, int y) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

int get_num(int x, int y) {
    return x * m + y;
}

void add_edge(int i, int j, int x, int y) {
    int u = get_num(i, j), v = get_num(x, y);
    g[u].push_back(v);
}


queue<pair<int, int>> q;

void upd(int v, int c, int d) {
    if (dist[v][c] == -1) {
        dist[v][c] = d;
        q.push({v, c});
    }
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    cin >> s;
    s += '*';
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            t += a[i][j];
            for (int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k];
                while (is_in(x, y) && a[x][y] == a[i][j]) {
                    x += dx[k];
                    y += dy[k];
                }
                if (!is_in(x, y)) {
                    continue;
                }
                add_edge(i, j, x, y);
            }
        }
    }
    ::memset(dist, -1, sizeof(dist));
    dist[get_num(0, 0)][0] = 0;
    q.push({get_num(0, 0), 0});
    while (!q.empty()) {
        auto [v, c] = q.front();
        q.pop();
        if (c == s.size()) {
            cout << dist[v][c] << "\n";
            exit(0);
        }
        if (t[v] == s[c]) {
            upd(v, c + 1, dist[v][c] + 1);
        }
        for (int to : g[v]) {
            upd(to, c, dist[v][c] + 1);
        }
    }
    exit(0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 109472kb

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

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

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: 4ms
memory: 109364kb

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #4:

score: 0
Accepted
time: 11ms
memory: 109600kb

input:

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

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

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: 28ms
memory: 109384kb

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: 7ms
memory: 109328kb

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: 7ms
memory: 109476kb

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: 0ms
memory: 109596kb

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: 109456kb

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: 271ms
memory: 109720kb

input:

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

output:

20003

result:

ok 1 number(s): "20003"

Test #15:

score: 0
Accepted
time: 254ms
memory: 109412kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA
ABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABA
ABABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

20001

result:

ok 1 number(s): "20001"

Test #16:

score: 0
Accepted
time: 20ms
memory: 109464kb

input:

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

output:

979905

result:

ok 1 number(s): "979905"

Test #17:

score: 0
Accepted
time: 371ms
memory: 109524kb

input:

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

output:

1650040

result:

ok 1 number(s): "1650040"

Test #18:

score: 0
Accepted
time: 424ms
memory: 109528kb

input:

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

output:

1810204

result:

ok 1 number(s): "1810204"

Test #19:

score: 0
Accepted
time: 355ms
memory: 109668kb

input:

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

output:

3270317

result:

ok 1 number(s): "3270317"