QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375204#4681. KeyboardingInfinityNS#AC ✓552ms102992kbC++142.0kb2024-04-02 23:33:262024-04-02 23:33:28

Judging History

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

  • [2024-04-02 23:33:28]
  • 评测
  • 测评结果:AC
  • 用时:552ms
  • 内存:102992kb
  • [2024-04-02 23:33:26]
  • 提交

answer

#include<bits/stdc++.h>

#define f first
#define s second
#define ll long long
#define ld long double
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;

int n,m;
bool inside(int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
vector<int> dx={1,-1,0,0},dy={0,0,1,-1};
int dist[51][51][10002];
pair<int,int> nxt[51][51][4];
int main(){
    scanf("%i %i",&n,&m);
    vector<string> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    string target;
    cin >> target;
    target+="*";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<4;k++){
                int x=i+dx[k],y=j+dy[k];
                while(1){
                    if(!inside(x,y)){
                        nxt[i][j][k]={-1,-1};
                        break;
                    }
                    if(a[i][j]!=a[x][y]){
                        nxt[i][j][k]={x,y};
                        break;
                    }
                    x+=dx[k];
                    y+=dy[k];
                }
            }
        }
    }
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<=sz(target);k++)dist[i][j][k]=INT_MAX;
    dist[0][0][0]=0;
    queue<pair<pair<int,int>,int>> q;
    q.push({{0,0},0});
    while(sz(q)){
        auto tr=q.front();
        q.pop();
        int x=tr.f.f,y=tr.f.s,k=tr.s;
        if(k==sz(target)){
            printf("%i\n",dist[x][y][k]);
            return 0;
        }
        for(int o=0;o<4;o++){
            if(nxt[x][y][o].f!=-1){
                int x2=nxt[x][y][o].f,y2=nxt[x][y][o].s;
                if(dist[x2][y2][k]>dist[x][y][k]+1){
                    dist[x2][y2][k]=dist[x][y][k]+1;
                    q.push({{x2,y2},k});
                }
            }
        }
        if(a[x][y]==target[k]){
            if(dist[x][y][k+1]>dist[x][y][k]+1){
                dist[x][y][k+1]=dist[x][y][k]+1;
                q.push({{x,y},k+1});
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

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

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #4:

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

input:

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

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

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

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

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

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

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

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

input:

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

output:

20003

result:

ok 1 number(s): "20003"

Test #15:

score: 0
Accepted
time: 464ms
memory: 102568kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA
ABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABA
ABABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

20001

result:

ok 1 number(s): "20001"

Test #16:

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

input:

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

output:

979905

result:

ok 1 number(s): "979905"

Test #17:

score: 0
Accepted
time: 518ms
memory: 102716kb

input:

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

output:

1650040

result:

ok 1 number(s): "1650040"

Test #18:

score: 0
Accepted
time: 552ms
memory: 102992kb

input:

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

output:

1810204

result:

ok 1 number(s): "1810204"

Test #19:

score: 0
Accepted
time: 507ms
memory: 102768kb

input:

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

output:

3270317

result:

ok 1 number(s): "3270317"