QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672683#4681. KeyboardingLJY_ljyAC ✓642ms122752kbC++112.2kb2024-10-24 18:07:282024-10-24 18:07:28

Judging History

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

  • [2024-10-24 18:07:28]
  • 评测
  • 测评结果:AC
  • 用时:642ms
  • 内存:122752kb
  • [2024-10-24 18:07:28]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int direct[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int MAXN = 60;
const int MAXM = 1e4 + 10;
const int INF = 1e9 + 10;

struct node {
	int x, y, num, step;
} A[MAXN][MAXN][4];

int r, c, minn[MAXN][MAXN][MAXM], len, ans;
char Map[MAXN][MAXN], str[MAXM];
queue<node> q;

bool legal(int x, int y) {
	if (1 <= x && x <= r && 1 <= y && y <= c) return true;
	return false;
}

void bfs() {
	minn[1][1][0] = 0;
	q.push((node){1, 1, 0, 0});
	while (!q.empty()) {
		node p = q.front();
		if (p.num == len) {
			ans = p.step;
			return;
		}
		q.pop();
		int nx = p.x, ny = p.y;
		if (Map[nx][ny] == str[p.num + 1]) {
			if (minn[nx][ny][p.num + 1] > p.step) {
				minn[nx][ny][p.num + 1] = p.step;
				q.push((node){nx, ny, p.num + 1, p.step});
			}
		}
		for (int i = 0; i < 4; i++) {
			if (A[p.x][p.y][i].step != -1) {
				nx = A[p.x][p.y][i].x, ny = A[p.x][p.y][i].y;
				if (Map[nx][ny] == str[p.num + 1]) {
					if (minn[nx][ny][p.num + 1] > p.step + 1) {
						minn[nx][ny][p.num + 1] = p.step + 1;
						q.push((node){nx, ny, p.num + 1, p.step + 1});
					}
				} 
				if (minn[nx][ny][p.num] > p.step + 1) {
					minn[nx][ny][p.num] = p.step + 1;
					q.push((node){nx, ny, p.num, p.step + 1});
				}
			}
		}
	}
} 

int main() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++)
			cin >> Map[i][j];
	}
	cin >> (str + 1);
	len = strlen(str + 1);
	str[len + 1] = '*';
	len++;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			for (int k = 0; k < MAXM; k++) {
				minn[i][j][k] = INF;
			}
		} 
	}
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			for (int k = 0; k < 4; k++) {
				int nx = i + direct[k][0], ny = j + direct[k][1];
				while (legal(nx, ny) && Map[nx][ny] == Map[i][j]) {
					nx += direct[k][0];
					ny += direct[k][1];
				}
				if (legal(nx, ny)) {
					A[i][j][k] = (node){nx, ny, 0, 0};
				} else {
					A[i][j][k] = (node){0, 0, 0, -1};
				}
			}
		}
	}
	bfs();
	cout << ans + len << endl;
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11796kb

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

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

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #4:

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

input:

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 2ms
memory: 12016kb

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

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

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

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

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

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

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

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

input:

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

output:

20003

result:

ok 1 number(s): "20003"

Test #15:

score: 0
Accepted
time: 483ms
memory: 122600kb

input:

50 50
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABA
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBABA
ABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABA
ABABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

20001

result:

ok 1 number(s): "20001"

Test #16:

score: 0
Accepted
time: 22ms
memory: 122752kb

input:

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

output:

979905

result:

ok 1 number(s): "979905"

Test #17:

score: 0
Accepted
time: 625ms
memory: 122576kb

input:

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

output:

1650040

result:

ok 1 number(s): "1650040"

Test #18:

score: 0
Accepted
time: 642ms
memory: 122580kb

input:

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

output:

1810204

result:

ok 1 number(s): "1810204"

Test #19:

score: 0
Accepted
time: 617ms
memory: 122464kb

input:

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

output:

3270317

result:

ok 1 number(s): "3270317"