#include #include #include #include using namespace std; #define INF 1023456789 int R,S,r,s,M; char v; int vstup[3][2047][2047]; int dist[2047][2047]; int prev[2047][2047]; int dy[] = {1,-1,0,0}; int dx[] = {0,0,1,-1}; char dc[] = "JSVZ"; int main() { scanf("%d %d %d %d %d", &R, &S, &r, &s, &M); // načtení vstupu a vytvoření tabulky for(int i = 0; i=0; --i) { for(int j = S-1; j>=0; --j) { vstup[1][i][j] = vstup[1][i][j+1] + vstup[0][i][j] - ((j+s F; dist[0][0] = 0; F.push(0); F.push(0); int x,y, xx, yy; while(!F.empty()) { y = F.front(); F.pop(); x = F.front(); F.pop(); if (y==R-r && x==S-s) { // zrekonstruování cesty vector vc; while( y!=0 || x!=0 ) { vc.push_back(dc[prev[y][x]]); yy = y-dy[prev[y][x]]; x = x-dx[prev[y][x]]; y = yy; } for(int i = vc.size()-2; i>=0; --i) printf("%c",vc[i]); printf("\n"); return 0; } for(int d = 0; d<4; d++) { yy = y+dy[d]; xx = x+dx[d]; // jsem vně místnosti, je tam moc překážek nebo jsem tam už byl if (xx<0 || yy<0 || xx>S-s || yy>R-r || vstup[2][yy][xx]>M || dist[yy][xx]<=dist[y][x]+1) continue; dist[yy][xx] = dist[y][x]+1; prev[yy][xx] = d; F.push(yy); F.push(xx); } } printf("Santa je chudak.\n"); return 0; }