立方体IV（暑假每日一题 10）

立方体IV（暑假每日一题 10）

Vincenzo 决定制作立方体 IV，但所有预算只够制作一个正方形迷宫。

每个房间里都有一个号码。

能够移动次数最多的人将获胜。

弄清楚谁将成为赢家，以及他将能够到达的房间数量。

输出格式 每组数据输出一个结果，每个结果占一行。

如果有多个人可到达的房间数相同，那么最初所在房间的房间号最小的人将获胜。

223 41 2 31 2 9 5 3 8 4 6 7

输出样例：

Case #1: 1 2Case #2: 6 4

#include#includeusing namespace std;const int N = 1010;int s;int g[N][N], f[N][N];int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};int get(int x, int y, int d){ if(f[x][y] != -1) return f[x][y]; int res = 0; for(int i = 0; i < 4; i++){ int a = x + dx[i], b = y + dy[i]; if(a >= 1 && a <= s && b >= 1 && b <= s && g[a][b] == g[x][y] + 1){ res = max(res, get(a, b, d + 1)); } } return f[x][y] = res + 1;}int main(){ int t; scanf("%d", &t); for(int k = 1; k <= t; k++){ scanf("%d", &s); for(int i = 1; i <= s; i++) for(int j = 1; j <= s; j++) scanf("%d", &g[i][j]); memset(f, -1, sizeof f); int sd = -1, d = -1; for(int i = 1; i <= s; i++) for(int j = 1; j <= s; j++){ int r = get(i, j, 1); if(r > d || r == d && sd > g[i][j]) sd = g[i][j], d = r; } printf("Case #%d: %d %d\n", k, sd, d); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。