QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#672600#4681. KeyboardingLJY_ljyWA 47ms30148kbC++111.7kb2024-10-24 17:42:472024-10-24 17:42:49

Judging History

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

  • [2024-10-24 17:42:49]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:30148kb
  • [2024-10-24 17:42:47]
  • 提交

answer

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

struct node {
	int x, y, num, step;
};

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;
int r, c, minn[MAXN][MAXN][MAXM], len, ans;
char Map[MAXN][MAXN], str[MAXM];
queue<node> q;

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

void bfs() {
	int cnt = 0;
	while (Map[1][1] == str[cnt + 1]) cnt++;
	q.push((node){1, 1, cnt, 0});
	minn[1][1][cnt] = 0;
	while (!q.empty()) {
		node p = q.front();
		if (p.num == len) {
			ans = p.step;
			return;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = p.x + direct[i][0], ny = p.y + direct[i][1];
			while (illegal(nx, ny) && Map[nx][ny] == Map[p.x][p.y]) {
				nx += direct[i][0];
				ny += direct[i][1];
			}
			if (illegal(nx, ny)) {
				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});
					}
				} else {
					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;
			}
		} 
	}
	bfs();
	cout << ans + len << endl;
	return 0;
} 

詳細信息

Test #1:

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

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

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

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #4:

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

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

input:

4 3
XYZ
AAA
CAD
B**
A

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

1 2
A*
A

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

2 1
*
A
A

output:

4

result:

ok 1 number(s): "4"

Test #8:

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

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: -100
Wrong Answer
time: 47ms
memory: 20212kb

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:

64235

result:

wrong answer 1st numbers differ - expected: '64174', found: '64235'