Lilypad Pond [Richard Ho, 2006]

FJ has installed a beautiful pond for his cows' aesthetic enjoyment and exercise. The rectangular pond has been partitioned into square cells of M rows and N columns (1 <= M <= 30; 1 <= N <= 30). Some of the cells have astonishingly sturdy lilypads; others have rocks; the remainder are just beautiful, cool, blue water. Bessie is practicing her ballet moves by jumping from one lilypad to another and is currently located at one of the lilypads. She wants to travel to another lilypad in the pond by jumping from one lilypad to another. Surprising only to the uninitiated, Bessie's jumps between lilypads always appear as a chess-knight's move: one move in one direction and then two more in the orthogonal direction (or perhaps two in one direction and then one in the orthogonal direction). Farmer John is observing Bessie's ballet drill and realizes that sometimes she might not be able to jump to her destination lilypad because intermediary lilypads are missing. Ever thrifty, he wants to place additional lilypads so she can complete her quest (perhaps quickly, perhaps by using a large number of intermediate lilypads). Of course, lilypads cannot be placed where rocks already intrude on a cell. Help Farmer John determine the minimum number of additional lilypads he has to place, and in how many ways he can place that minimum number. PROBLEM NAME: lilypad INPUT FORMAT: * Line 1: Two space-separated integers: M and N * Lines 2..M+1: Line i+1 describes row i of the pond using N space-separated integers with these values: 0 indicates empty water; 1 indicates a lilypad in place; 2 indicates rock in place; 3 indicates the lilypad Bessie starts on; 4 indicates the lilypad Bessie wants to travel to. SAMPLE INPUT (file lilypad.in): 4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0 INPUT DETAILS: The ponds has 4 rows and 5 columns. Bessie is at row 2 column 1, and she wants to reach row 4 column 4. A rock and three lilypads are present. OUTPUT FORMAT: * Line 1: One integer: the minimum number of additional lilypads required. If it is not possible to help Bessie jump to her destination, print -1. * Line 2: One integer: the total number of possible ways the additional lilypads can be positioned. This number is guaranteed to fit into a single 64-bit signed integer. Do not output this line if line 1 contains -1. SAMPLE OUTPUT (file lilypad.out): 2 3 OUTPUT DETAILS: Two lilypads are required. There are three ways to place them: row 4 column 2 and row 2 column 3; row 1 column 3 and row 3 column 2; or row 1 column 3 and row 2 column 5: R1C2,R2C3 R1C3,R3C2 R1C3,R2C5 1 0 0 0 0 1 0 X 0 0 1 0 X 0 0 3 0 X 0 0 3 0 0 0 0 3 0 0 0 X 0 0 2 0 0 0 X 2 0 0 0 0 2 0 0 0 X 0 4 0 0 0 0 4 0 0 0 0 4 0

ტბორი შროშანის ფოთლებით – გოგა კორელის თარგმანი

ძროხების ესთეტიური სიამოვნებისთვის FJ-მ გააკეთა ლამაზი ტბორი. მართკუთხა ფორმის გუბურა დაჰყო კვადრატულ უჯრებად, M ცალი სტრიქონი და N ცალი სვეტი (1 <= M <= 30; 1 <= N <= 30). ზოგიერ უჯრაზე არის შროშანის ფოთოლი, ზოგიერთზე ქვა, ხოლო დანარჩენებზე უბრალოდ ლამაზი ლურჯი წყალი. ბესი ბალეტში ვარჯიშობს და ცდილობს ერთი ფოთლიდან მეორეზე გადახტეს, ხოლო ახლა ის ერთ ერთ შროშანის ფოთოლზე დგას. მას უნდა, რომ ერთ ფოთოლთან მიაღწიოს მხოლოდ ფოთლებზე გადახტომით. ბესის სვლები არის ჭადრაკის ცხენის სვლების მსგავსი. მისი ნახტომი ყოველთვის არის ერთი უჯრა რომელიმე მიმართულებით და ორი მის მართობულად ან ორი უჯრა რომელიმე მიმართულებით და ერთი მის მართობულად. ფერმერი ჯონი აკვირდება ბესის და ხვდება, რომ ხანდახან ბესი დანიშნულების ადგილს ვერ აღწევს, რადგან შუამავალი ფოთლები არ არსებობენ საბოლოო ფოთოლსა და ბესის შორის. ამის გამო ჯონს უნდა, რომ დაალაგოს შუამავალი ფოთლები, რათა ბესიმ დაასრულოს თავისი მისია. რა თქმა უნდა, შროშანის ფოთოლს ვერ დავდებთ იქ, სადაც უკვე ქვა არის. დავეხმაროთ ფერმერ ჯონს დაადგინოს მინიმალური რაოდენობა დამატებითი ფოთლებისა რომელიც მან უნდა დადოს, რომ ბესიმ მიაღწიოს გამიზნულ ფოთოლს და რამდენნაირად შეუძლია მას ამ მინიმალური რაოდენობის ფოთლების განთავსება. შემომავალი მონაცემები: ხაზი 1 - 2 ცალი ცარიელი უჯრის გამოტოვებით დაწერილი ინტი : M და N. მომდევნი M ცალი ხაზი - N ცალი ცარიელი უჯრის გამოტოვებით დაწერილი ინტი : 0 ნიშნავს ცარიელს, წყალს; 1 ნიშნავს შროშანის ფოთოლს; 2 ნიშნავს ქვას; 3 ნიშნავს, რომ ამ ფოთოლზე დგას ბესი; 4 მიუთითებს ფოთოლს რომელზეც ბესი უნდა მივიდეს. მაგალითი: 4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0 დეტალები: ტბორს აქვს 4 სვეტი და 5 სტრიქონი გამომავალი მონაცემები: ხაზი 1 - 1 ცალი ინტი (მინიმალური რაოდენობა დასამატებელი ფოთლებისა, რომ ბესიმ მიაღწიოს დანიშნულების ადგილას, თუ შეუძლებელია დაბეჭდეთ -1) ხაზი 2 - 1 ცალი ინტი (სულ რამდენნაირად შეიძლება ამ მინიმალური რაოდენობის ფოთლების განლაგება, ყველა ვარიანტი. ეს რიცხვი ზუსტად ეტევა ინტში. არ დაბეჭდოთ მეორე ხაზი, თუ პირველში დაბეჭდავთ -1) მაგალითის პასუხი: 2 3 გამომავალი პასუხის დეტალი: მინიმუმ 2 ცალი ფოთოლი არის საჭირო და მათი დალაგება 3 გზით არის შესაძლებელი. 1) სტრიქონი 4, სვეტი 2 და სტრიქონი 2, სვეტი 3 2) სტრიქონი 1, სვეტი 3 და სტრიქონი 3, სვეტი 2 3) სტრიქონი 1, სვეტი 3 და სტრიქონი 2, სვეტი 5

lilypad

It suffices to consider the grid as a graph and the possible jumps as edges. Then the problem becomes: Given a graph where some vertices are marked, find the least number of additional vertices to mark so there exist a path between s and t. First notice that each connected component can be 'shrinked' into one vertex which combines all the edges of the vertices it contains as we could walk around the component free of cost. The standard way to go here is to construct some kind of weight on the edges to change the problem into finding the shortest path and counting the number of shortest paths. It follows that the distance should be the least number of vertices that needs to be marked Clearly, any edge from an unmarked vertex to an unmarked vertex has cost one as another vertex needs to be marked. Things gets tricky in situations where a marked vertex is traversed, namely the following situations: v1, v2 are marked, a and b are not. The following edges exist: a->v1, a->v2, v1->b, v2->b Then any kind of shortest path which involves v1 and v2 would end up calculating the same set of unmarked vertices (a and b) twice since there are two paths. Therefore, it's necessary to 'skip' marked vertices by having a path of length 1 directly from a to b. It's quite clear that the least number of vertices to be marked equals the shortest distance from s to t minus one (the last edge to t should be free). To get the answers, do a BFS from s, then go through each vertex in order and count the number of paths by summing the paths that lead to of all its neighbors which are distance d-1 away (assuming this vetex has distance d from s). Here is 1000 point scorer Yang Yi's solution, which might or might not match the description above: #include <stdio.h> #include <queue> #include <fstream> #define MAXN 30 using namespace std; FILE *in; int fx[8] = {-2,-1,+1,+2,+2,+1,-1,-2}; int fy[8] = {-1,-2,-2,-1,+1,+2,+2,+1}; int m,n,sx,sy,ex,ey; int data[MAXN][MAXN]; int rea[MAXN][MAXN][MAXN][MAXN]; int dist[MAXN][MAXN]; long long counter[MAXN][MAXN]; queue<pair<int, int> > Q; void init () { int i, j; in = fopen("lilypad.in","r"); fscanf(in,"%d%d",&m,&n); for (i = 0; i < m; i ++) for (j = 0; j < n; j ++) { fscanf(in,"%d",data[i] + j); if (data[i][j] == 3) { data[i][j] = 0; sx = i; sy = j; } if (data[i][j] == 4) { data[i][j] = 0; ex = i; ey = j; } } fclose(in); } void solve () { int i, j, x, y; memset(rea, 0, sizeof(rea)); for (i = 0; i < m; i ++) for (j = 0; j < n; j ++) if (data[i][j] == 0) { // printf("i j %d %d\n",i,j); Q.push(make_pair(i,j)); rea[i][j][i][j] = 1; while (!Q.empty()) { x=Q.front().first; y=Q.front().second; Q.pop(); for (int k = 0; k < 8; k ++) if (x + fx[k] >= 0 && x + fx[k] < m && y + fy[k] >= 0 && y + fy[k] < n && data[x+fx[k]][y+fy[k]] == 1 && rea[i][j][x+fx[k]][y+fy[k]] == 0) { Q.push(make_pair(x + fx[k], y + fy[k])); rea[i][j][x+fx[k]][y+fy[k]] = 1; } } for (x = 0; x < m; x ++) for (y = 0; y < n; y ++) if (rea[i][j][x][y] == 1) { // printf("Lily Reachable %d %d\n",x,y); for (int k = 0; k < 8; k ++) if (x + fx[k] >= 0 && x + fx[k] < m && y + fy[k] >= 0 && y + fy[k] < n && data[x+fx[k]][y+fy[k]] == 0 && rea[i][j][x+fx[k]][y+fy[k]] == 0) rea[i][j][x+fx[k]][y+fy[k]] = 2; } } memset(dist, -1, sizeof(dist)); dist[sx][sy] = 0; counter[sx][sy] = 1; Q.push(make_pair(sx,sy)); while (!Q.empty()) { x=Q.front().first; y=Q.front().second; Q.pop(); // printf("%d %d : %d %I64d\n",x,y,dist[x][y],counter[x][y]); for (i = 0; i < m; i ++) for (j = 0; j < n; j ++) if (rea[x][y][i][j] == 2) { // printf("(%d %d) -> (%d %d)\n",x,y,i,j); if (dist[i][j] == -1) { dist[i][j] = dist[x][y] + 1; counter[i][j] = counter[x][y]; Q.push(make_pair(i,j)); } else if (dist[i][j] == dist[x][y] + 1) counter[i][j] += counter[x][y]; } } // while (1); } void output () { ofstream fout("lilypad.out"); if (dist[ex][ey] == -1) fout<<-1<<endl; else fout<<dist[ex][ey] - 1<<endl<<counter[ex][ey]<<endl; } int main () { init(); solve(); output(); return 0; }

lilypad – გოგა კორელის თარგმანი

ეს უჯრებიანი მართკუთხედი წარმოვიდგინოთ როგორც გრაფი და შესაძლო გადახტომები როგორც წიბოები. ჩვენი ამოცანაა, რომ მოცემული გრაფისთვის სადაც ზოგიერთი წვერო მონიშნულია, ვიპოვოთ მინიმალური რაოდენობა დამატებითი წვეროებისა რომელთა მონიშვნით იარსებებს გზა s-დან t-მდე. პირველად შევნიშნოთ, რომ თითოეული ბმული კომპონენტი შეიძლება შევამციროთ და აღვიქვათ ერთ წვეროდ რადგანაც ასე რომ ვთქვათ უფასოდ შეგვიძლია მოძრაობა ამ კომპონენტის წვეროებში. ბმული კომპონენტი შეიცავს მის წიბოებს და წვეროებს. ჩვენი მიზანია რაღაც პრინციპით წიბოებს განვუსაზღვროთ წონები ამით ჩვენი ამოცანა გახდება ვიპოვოთ მოკლე გზა და დავთვალოთ ამ მოკლე გზების რაოდენობა. მანძილი იქნება უმცირესი რაოდენობა წვეროებისა რასაც სჭირდება მონიშვნა. რა საკვირველია მოუნიშნავი წვეროდან მოუნიშნავ წვეროში მისვლა ღირს 1, რადგან ერთი წვეროს მონიშვნა ანუ იმ ადგილას ფოთლის დადება არის საჭირო. რთულდება სიტუაცია როდესაც უკვე მონიშნულ წვეროს გავდივართ. მაგალითად: v1, v2 არიან მონიშნულები, ხოლო a და b არა. მისვლა შესაძლებელია : a -> v1 , a -> v2 , v1->b , v2 -> b ასე რომ ნებისმიერი უმოკლესი გზა რომელიც შეიცავს v1-ს და v2-ს, ორჯერ მონიშნავდა a-ს და b-s რადგან a-დან b-მდე მისასვლელი ორი გზა არსებობს, მაგრამ რეალურად ეს უნდა გავითვალისწინოთ : ეს სხვადასხვა გზები არის მაგრამ ვნიშნავთ ორივე შემთხვევაში ერთი და იგივე წერტილებს (a-ს და b-ს) ასე რომ ეს პასუხში არ უნდა მივამატოთ როგორც სხვა უმოკლესი გზა. ამის თავიდან ასარიდებლად უკვე მონიშნულ წერტილები უნდა 'გამოვტოვოთ' და a-დან b-მდე პირდაპირ გვექნება გზა სიგრძით 1. უმცირესი რაოდენობა მოსანიშნი წვეროებისა იქნება უმცირესი გზის სიგრძეს s-დან t-მდე მინუს ერთის ტოლი. (ბოლო წიბო t-მდე უნდა იყოს თავისუფალი) რომ მივიღოთ პასუხი გავუშვებთ BFS-ს s წერტილიდან თანმიმდევრულად გავუყვებით ყველა წვეროს და დავთვლით იმ გზებს რომლებიც s წერტილიდან d მინუს 1 მანძილით არიან დაშორებულები. ( მივიჩნევთ რომ ეს წვერო s წერტილიდან d - ს ტოლი მანძილით არის დაშორებული) ქვევით მოცემულია Yang Yi -ს ამოხსნა, რომელმაც 1000 ქულა დაიმსახურა. ეს ამოხსნა შეიძლება დაემთხვას ან არ დაემთხვას ზევით მოცემულ აღწერას.

Here is 1000 point scorer Yang Yi's solution

#include <stdio.h>
#include <queue>
#include <fstream>
#define MAXN 30

using namespace std;

FILE *in;
int fx[8] = {-2,-1,+1,+2,+2,+1,-1,-2};
int fy[8] = {-1,-2,-2,-1,+1,+2,+2,+1};
int m,n,sx,sy,ex,ey;
int data[MAXN][MAXN];
int rea[MAXN][MAXN][MAXN][MAXN];
int dist[MAXN][MAXN];
long long counter[MAXN][MAXN];
queue<pair<int, int> > Q;

void init () {
    int i, j;
    
    in = fopen("lilypad.in","r");
    fscanf(in,"%d%d",&m,&n);
    for (i = 0; i < m; i ++)
        for (j = 0; j < n; j ++) {
            fscanf(in,"%d",data[i] + j);
            if (data[i][j] == 3) {
                data[i][j] = 0;
                sx = i;
                sy = j;
                }
            if (data[i][j] == 4) {
                data[i][j] = 0;
                ex = i;
                ey = j;
                }
            }
    fclose(in);
    }

void solve () {
    int i, j, x, y;
    
    memset(rea, 0, sizeof(rea));
    for (i = 0; i < m; i ++)
        for (j = 0; j < n; j ++)
            if (data[i][j] == 0) {
//                printf("i j %d %d\n",i,j);
                Q.push(make_pair(i,j));
                rea[i][j][i][j] = 1;
                while (!Q.empty()) {
                    x=Q.front().first;
                    y=Q.front().second;
                    Q.pop();
                    for (int k = 0; k < 8; k ++)
                        if (x + fx[k] >= 0 && x + fx[k] < m && y + fy[k] >= 0 && y + fy[k] < n && data[x+fx[k]][y+fy[k]] == 1 && rea[i][j][x+fx[k]][y+fy[k]] == 0) {
                            Q.push(make_pair(x + fx[k], y + fy[k]));
                            rea[i][j][x+fx[k]][y+fy[k]] = 1;
                            }
                    }
                for (x = 0; x < m; x ++)
                    for (y = 0; y < n; y ++)
                        if (rea[i][j][x][y] == 1) {
//                            printf("Lily Reachable %d %d\n",x,y);
                            for (int k = 0; k < 8; k ++)
                                if (x + fx[k] >= 0 && x + fx[k] < m && y + fy[k] >= 0 && y + fy[k] < n && data[x+fx[k]][y+fy[k]] == 0 && rea[i][j][x+fx[k]][y+fy[k]] == 0)
                                    rea[i][j][x+fx[k]][y+fy[k]] = 2;
                            }
                }
    
    memset(dist, -1, sizeof(dist));
    dist[sx][sy] = 0;
    counter[sx][sy] = 1;
    Q.push(make_pair(sx,sy));
    while (!Q.empty()) {
        x=Q.front().first;
        y=Q.front().second;
        Q.pop();
        
//        printf("%d %d : %d %I64d\n",x,y,dist[x][y],counter[x][y]);
        
        for (i = 0; i < m; i ++)
            for (j = 0; j < n; j ++)
                if (rea[x][y][i][j] == 2) {
//                    printf("(%d %d) -> (%d %d)\n",x,y,i,j);
                    if (dist[i][j] == -1) {
                        dist[i][j] = dist[x][y] + 1;
                        counter[i][j] = counter[x][y];
                        Q.push(make_pair(i,j));
                        }
                    else
                        if (dist[i][j] == dist[x][y] + 1)
                            counter[i][j] += counter[x][y];
                    }
        }
//    while (1);
    }

void output () {
    ofstream fout("lilypad.out");
    
    if (dist[ex][ey] == -1)
        fout<<-1<<endl;
    else
        fout<<dist[ex][ey] - 1<<endl<<counter[ex][ey]<<endl;
    }

int main () {
    
    init();
    solve();
    output();
    
    return 0;
    }