QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#18332#2265. Short Codinglinmuhan#WA 8ms3840kbC++143.5kb2022-01-17 21:21:232022-05-04 17:58:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 17:58:28]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3840kb
  • [2022-01-17 21:21:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 12;
const int dx[5][2] = {{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int n, m, Ans = 5;
int xs, ys, xt, yt;
string dic[N * 2] = {"LEFT", "RIGHT", "IF_OPEN 1", "IF_OPEN 2", "IF_OPEN 3"
, "IF_OPEN 4", "GOTO 1", "GOTO 2", "GOTO 3", "GOTO 4", "FORWARD"};
string opt[N * 2], ans[N * 2];
char s[N][N];
bool f[N][N][N][N], Flag, BUHEFA;
bool valid (int x, int y) {return (x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] != '#');}
void dfss (int x, int y, int stp, int dir, int lim) {
	if (Flag) return ;
	if (stp == lim + 1) stp = 1;
	if (x == xt && y == yt) {
		Flag = 1;
		return ;
	}
	if (f[x][y][stp][dir]) {
		BUHEFA = 1;
		return ;
	}
	f[x][y][stp][dir] = 1;
	if (opt[stp] == "LEFT") {
		dir --;
		if (dir == 0) dir = 4;
		dfss (x, y, stp + 1, dir, lim);
	}
	if (opt[stp] == "RIGHT") {
		dir ++;
		if (dir == 5) dir = 1;
		dfss (x, y, stp + 1, dir, lim);
	}
	if (opt[stp] == "GOTO 1") {
		if (lim >= 1) {
			dfss (x, y, 1, dir, lim);
		} else {
			BUHEFA = 1;
		}
	}
	if (opt[stp] == "GOTO 2") {
		if (lim >= 2) {
			dfss (x, y, 2, dir, lim);
		} else {
			BUHEFA = 1;
		}
	}
	if (opt[stp] == "GOTO 3") {
		if (lim >= 3) {
			dfss (x, y, 3, dir, lim);
		} else {
			BUHEFA = 1;
		}
	}
	if (opt[stp] == "GOTO 4") {
		if (lim >= 4) {
			dfss (x, y, 4, dir, lim);
		} else {
			BUHEFA = 1;
		}
	}
	if (opt[stp] == "IF_OPEN 1") {
		int xx = x + dx[dir][0], yy = y + dx[dir][1];
		if (valid (xx, yy)) {
			if (lim >= 1) {
				dfss (x, y, 1, dir, lim);
			} else {
				BUHEFA = 1;
			}
		} else {
			dfss (x, y, stp + 1, dir, lim);
		}
	}
	if (opt[stp] == "IF_OPEN 2") {
		int xx = x + dx[dir][0], yy = y + dx[dir][1];
		if (valid (xx, yy)) {
			if (lim >= 2) {
				dfss (x, y, 2, dir, lim);
			} else {
				BUHEFA = 1;
			}
		} else {
			dfss (x, y, stp + 1, dir, lim);
		}
	}
	if (opt[stp] == "IF_OPEN 3") {
		int xx = x + dx[dir][0], yy = y + dx[dir][1];
		if (valid (xx, yy)) {
			if (lim >= 3) {
				dfss (x, y, 3, dir, lim);
			} else {
				BUHEFA = 1;
			}
		} else {
			dfss (x, y, stp + 1, dir, lim);
		}
	}
	if (opt[stp] == "IF_OPEN 4") {
		int xx = x + dx[dir][0], yy = y + dx[dir][1];
		if (valid (xx, yy)) {
			if (lim >= 4) {
				dfss (x, y, 4, dir, lim);
			} else {
				BUHEFA = 1;
			}
		} else {
			dfss (x, y, stp + 1, dir, lim);
		}
	}
	if (opt[stp] == "FORWARD") {
		int xx = x + dx[dir][0], yy = y + dx[dir][1];
		if (valid (xx, yy)) {
			dfss (xx, yy, stp + 1, dir, lim);
		} else {
			dfss (x, y, stp + 1, dir, lim);
		}
	}
}
bool chk (int len) {
	if (len == 4 && opt[1] == "RIGHT" && opt[2] == "RIGHT" && opt[3] == "FORWARD" && opt[4] == "GOTO 2") {
		len ++;
		len --;
	}
	memset (f, 0, sizeof f);
	Flag = 0; BUHEFA = 0;
	dfss (xs, ys, 1, 3, len);
	return Flag && (! BUHEFA);
}
void dfs (int dep) {
	if (dep > 5) return ;
	if (dep > Ans) return ;
	if (chk (dep - 1)) {
		if (Ans > dep - 1) {
			Ans = dep - 1;
			for (int i=1;i<=dep-1;i++) ans[i] = opt[i];
		}
	}
	for (int i=0;i<11;i++) {
		opt[dep] = dic[i];
		dfs (dep + 1);
	}
}
int main () {
	cin >> n >> m;
	for (int i=1;i<=n;i++) scanf ("%s", (s[i] + 1));
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			if (s[i][j] == 'S') xs = i, ys = j;
			if (s[i][j] == 'G') xt = i, yt = j;
		}
	}
	dfs (1);
	if (Ans < 5) {
		cout << Ans << endl;
		for (int i=1;i<=Ans;i++) cout << ans[i] << endl;
		return 0;
	}
	puts ("5");
	puts ("LEFT");
	puts ("IF_OPEN 5");
	puts ("RIGHT");
	puts ("GOTO 2");
	puts ("FORWARD");
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3776kb

input:

4 2
S#
.#
.#
G.

output:

1
FORWARD

result:

ok correct answer!

Test #2:

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

input:

3 6
##S..#
#..##.
.G..#.

output:

2
FORWARD
RIGHT

result:

ok correct answer!

Test #3:

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

input:

3 7
....S##
.#.#...
##.#.G#

output:

2
FORWARD
LEFT

result:

ok correct answer!

Test #4:

score: 0
Accepted
time: 8ms
memory: 3708kb

input:

4 8
...S.#.#
##..#.#.
###...#.
#.#.#G.#

output:

3
FORWARD
FORWARD
LEFT

result:

ok correct answer!

Test #5:

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

input:

3 5
.S#..
.....
..#G.

output:

3
FORWARD
LEFT
FORWARD

result:

ok correct answer!

Test #6:

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

input:

10 10
.....S#...
...#......
....##....
.#.....#..
....#.....
..#.......
...#......
..........
.#...#....
G.#..#...#

output:

3
LEFT
FORWARD
IF_OPEN 2

result:

wrong answer unauthorized token IF_OPEN