#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
const int N = 35;
char v[N][N], ans[2*N];
ll dp[N][N];
int n, m, l;
ll dprec(int x, int y){
int ind = x + y;
if(ans[ind] != '*' and ans[ind] != v[x][y]){
return 0;
}
if(x == n-1 and y == m-1){
return 1;
}
if(dp[x][y] < 0){
return dp[x][y];
}
dp[x][y] = 0;
if(x + 1 < n){
dp[x][y] += dprec(x + 1, y);
}
if(y + 1 < m){
dp[x][y] += dprec(x, y + 1);
}
return dp[x][y];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m;
l = n + m - 1;
rep(i, 0, n) rep(j, 0, m) cin >> v[i][j];
ll k; cin >> k;
rep(i, 0, l) ans[i] = '*';
ans[0] = v[0][0];
rep(i, 1, l) rep(j, 0, 26){
ans[i] = j + 'a';
memset(dp, -1, sizeof dp);
if(dprec(0, 0) >= k) break;
k -= dprec(0, 0);
}
cout << ans << '\n';
}
Compilation message
kthpath.cpp: In function 'void usaco(std::string)':
kthpath.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
13 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kthpath.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
14 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
