QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356530#4681. KeyboardingUFRJ#WA 1ms3992kbC++202.4kb2024-03-17 22:16:232024-03-17 22:16:24

Judging History

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

  • [2024-03-17 22:16:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3992kb
  • [2024-03-17 22:16:23]
  • 提交

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>;
    vector<T> bfs;
    if(keys[0][0] == s[0]){
        bfs = {{0,0,1}};
        dist[0][0][1] = 0;
    } else {
        bfs = {{0,0,0}};
        dist[0][0][0] = 0;
    }
    int64_t answer = -1;
    for(int _=0; _ < int(bfs.size()); _++){
        auto [i, j, t] = bfs[_];
        //cerr<<i<<" "<<j<<" "<<t<<" = "<<dist[i][j][t]<<"\n";
        if(t == sz && keys[i][j] == '*'){
            answer = dist[i][j][t];
            break;
        }
        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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

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

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #4:

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

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

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3596kb

input:

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

output:

9

result:

wrong answer 1st numbers differ - expected: '5', found: '9'