Date | Problem | Judgement | Runtime | Language | Test cases | |
|---|---|---|---|---|---|---|
| 12:38:33 | Planet Hopping | Accepted | 0.00 s | C++ | 23/23 | |
Idea: DP Top down
- If see hard to DP, you should try DFS fist
- DFS can pass 22/23 testcase, and you only need update memory to use DP Top down
Code DP:
#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[22][22];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int F[22][22][402];
int dfs(int u, int v, int m){
if (m < 0) return 0;
if (F[u][v][m] != -1) return F[u][v][m];
int rs = a[u][v];
for(int i=0; i<=3; i++){
int x = u + dx[i];
int y = v + dy[i];
if (x < 1 || x > n || y < 1 || y > n || a[x][y] <= a[u][v]) continue;
rs = max(rs, a[u][v] + dfs(x, y, m-1));
}
return F[u][v][m] = rs;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin >> a[i][j];
memset(F, -1, sizeof(F));
for (int i = 1; i <= n; i++) {
ans = max(ans, dfs(1, i, m));
ans = max(ans, dfs(n, i, m));
ans = max(ans, dfs(i, 1, m));
ans = max(ans, dfs(i, n, m));
}
cout<<ans;
}
| 12:02:51 | Time Limit Exceeded | > 1.00 s | C++ | Diff with this submission | 22/23 | View Details | |
Code DFS:
#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool visited[100][100];
void reset(){
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
visited[i][j] = false;
}
void dfs(int u, int v, int m, int s){
if (m < 0) return;
ans = max(ans, s);
visited[u][v] = true;
for(int i=0; i<=3; i++){
int x = u + dx[i];
int y = v + dy[i];
if (x < 1 || x > n || y < 1 || y > n || visited[x][y] || a[x][y] <= a[u][v]) continue;
dfs(x, y, m-1, s+a[x][y]);
visited[x][y] = false;
}
}
int main(){
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin >> a[i][j];
for(int i=1; i<=n; i++) {
reset();
dfs(1,i,m,a[1][i]);
}
for(int i=1; i<=n; i++) {
reset();
dfs(i,1,m,a[i][1]);
}
for(int i=1; i<=n; i++) {
reset();
dfs(i,n,m,a[i][n]);
}
for(int i=1; i<=n; i++) {
reset();
dfs(n,i,m,a[n][i]);
}
cout<<ans;
}