QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356536#4681. KeyboardingUFRJ#AC ✓875ms202840kbC++202.4kb2024-03-17 22:31:182024-03-17 22:31:19

Judging History

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

  • [2024-03-17 22:31:19]
  • 评测
  • 测评结果:AC
  • 用时:875ms
  • 内存:202840kb
  • [2024-03-17 22:31:18]
  • 提交

answer

#include "bits/stdc++.h"

#define watch(x) cout << (#x) << " is " << (x) << endl

using namespace std;
using i64 = int64_t;


int n, m;
vector<string> keys;
vector<vector<vector<pair<int,int>>>> g;

bool is_safe(int i, int j) {
  return i >= 0 and i < n and j >= 0 and j < m;
}

vector<pair<int,int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void build() {

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {

      char cur = keys[i][j];
      for(auto &move : moves) {
        int ni = i, nj = j;

        while(is_safe(ni+move.first, nj+move.second)) {
          ni += move.first;
          nj += move.second;
          if(keys[ni][nj] != cur) break;
        }


        if(keys[ni][nj] != cur) {
          g[i][j].push_back({ni, nj});
        }
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false); 

  cin >> n >> m;
  keys.resize(n);
  g.assign(n, vector<vector<pair<int,int>>>(m));
  for(int i = 0; i < n; i++) cin >> keys[i];

  build();


//   for(int i = 0; i < n; i++) {
//     for(int j = 0; j < m; j++) {
//       cout << "From: " << i << " " << j << endl;
//       cout << "Edges:\n";
//       for(auto &e : g[i][j]) {
//         cout << e.first << " " << e.second << endl;
//       }
//     }  
//   }
//   return 0;
    string s; cin>>s;
    s += '*';
    const int sz = int(s.size());
    vector dist(n, vector(m, vector<int64_t>(sz + 1, -1)));
    
    using T = tuple<int, int, int>;
    deque<T> bfs;
    bfs.push_front({0,0 ,0});
    dist[0][0][0] = 0;
    int64_t answer = -1;
    while(!bfs.empty()){
        auto [i, j, t] = bfs.front();
        bfs.pop_front();
        //cerr<<i<<" "<<j<<" "<<t<<" = "<<dist[i][j][t]<<"\n";
        if(t == sz && keys[i][j] == '*'){
            answer = dist[i][j][t];
            break;
        }
        if(t < sz && keys[i][j] == s[t] && dist[i][j][t+1] == -1){
            dist[i][j][t+1] = dist[i][j][t];
            bfs.push_front({i,j,t+1});
        }
        for(auto &[a, b] : g[i][j]){
            if(dist[a][b][t] == -1){
                dist[a][b][t] = dist[i][j][t] + 1;
                bfs.push_back({a,b,t});
            }
            if(t < sz && keys[a][b] == s[t] && dist[a][b][t+1] == -1){
                dist[a][b][t+1] = dist[i][j][t] + 1;
                bfs.push_back({a,b,t+1});
            }
        }
    }

    cout<<answer + sz<<"\n";



    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3612kb

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #4:

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

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

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

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

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

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

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

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

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

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

input:

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

output:

20003

result:

ok 1 number(s): "20003"

Test #15:

score: 0
Accepted
time: 719ms
memory: 202708kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA
ABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABA
ABABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

20001

result:

ok 1 number(s): "20001"

Test #16:

score: 0
Accepted
time: 35ms
memory: 202708kb

input:

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

output:

979905

result:

ok 1 number(s): "979905"

Test #17:

score: 0
Accepted
time: 874ms
memory: 202692kb

input:

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

output:

1650040

result:

ok 1 number(s): "1650040"

Test #18:

score: 0
Accepted
time: 875ms
memory: 202708kb

input:

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

output:

1810204

result:

ok 1 number(s): "1810204"

Test #19:

score: 0
Accepted
time: 838ms
memory: 202840kb

input:

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

output:

3270317

result:

ok 1 number(s): "3270317"