QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672647#4681. KeyboardingLJY_ljyWA 1ms15896kbC++111.9kb2024-10-24 17:56:382024-10-24 17:56:38

Judging History

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

  • [2024-10-24 17:56:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:15896kb
  • [2024-10-24 17:56:38]
  • 提交

answer

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

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

const int direct[5][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 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 + 1) {
				minn[nx][ny][p.num + 1] = p.step + 1;
				q.push((node){nx, ny, p.num + 1, p.step + 1});
			}
		}
		for (int i = 0; i < 4; i++) {
			int nx = p.x + direct[i][0], ny = p.y + direct[i][1];
			while (legal(nx, ny) && Map[nx][ny] == Map[p.x][p.y]) {
				nx += direct[i][0];
				ny += direct[i][1];
			}
			if (legal(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});
					}
				}
				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;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

output:

30

result:

ok 1 number(s): "30"

Test #2:

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

input:

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

output:

160

result:

ok 1 number(s): "160"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 9972kb

input:

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

output:

20

result:

wrong answer 1st numbers differ - expected: '19', found: '20'