The Umbrella Problem: 2054

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
 This problem has been solved by kerry.

 Sorter: mlc413 Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1301

The Umbrella Problem: 2054 is problem number 1301 on the Peking University ACM site.

Solved! So, my strategy was to read the input and record the number and position of the lemming, lasers, and lava pits. Then I make a representation of the board state at each time point in an array called "safe", which is set up as "safe[timepoint][column][row]". 1 means that square is safe at that timepoint, 0 means it is not safe. Then I just loop through the timepoints, checking at each step to see if there is any legal safe move at the next step. I store spaces in the current row that could have been legally reached in the 1d array "this[column]" (row is not needed, as the row is the current row, equal to the current timepoint). Then I compute the locations in the next row that can be reached legally from the points in the "this" array, storing them in "next[column]". If there are no legal next moves, return "GARRET", meaning impossible to finish. If you can get all the way to the last row and you have at least one legal move, then return "FERRET", or possible. Time should be O(col*row^2), since the number of rows==the number of timepoints. The max columns and rows are 10, so this is acceptable.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct location {
int col;
int row;
};

int main() {

char size[12], *board[10], safe[10][10][10], end, this[10], next[10];
int col, row, i, j, k, grassnum, lavanum, lasernum;
struct location lemming, lava[10], grass[10], laser[100];
while (1) {
for(i=0;i<10;i++)
for(j=0;j<10;j++)
for(k=0;k<10;k++) {
safe[i][j][k]=1;
this[k]=0;
next[k]=0;
}
grassnum = lavanum = lasernum = 0;
scanf("%s %d %d\n", size, &col, &row);
if (!(strcmp(size, "ENDOFINPUT"))) {
return 0;
}
for (i=0;i<row;i++) {
board[i]=(char *)malloc(sizeof(char)*(col+2));
fgets(board[i], col+2, stdin);
}
for(i=0;i<row;i++) {
for(j=0;j<col;j++) {
switch(board[i][j]) {
case 'L':
lemming.row=i;
lemming.col=j;
break;

case 'S':
laser[lasernum].row=i;
laser[lasernum].col=j;
lasernum++;
break;

case 'P':
lava[lavanum].row=i;
lava[lavanum].col=j;
lavanum++;
break;

case 'G':
grass[grassnum].row=i;
grass[grassnum].col=j;
grassnum++;
break;

default:
break;
}
}
}

for(i=0;i<lasernum;i++) {
for(j=laser[i].row;j>=0;j--) {
safe[0][laser[i].col][j]=0;
safe[3][laser[i].col][j]=0;
safe[4][laser[i].col][j]=0;
safe[7][laser[i].col][j]=0;
safe[8][laser[i].col][j]=0;
}
for(j=laser[i].col;j<10;j++) {
safe[0][j][laser[i].row]=0;
safe[1][j][laser[i].row]=0;
safe[4][j][laser[i].row]=0;
safe[5][j][laser[i].row]=0;
safe[8][j][laser[i].row]=0;
safe[9][j][laser[i].row]=0;
}
for(j=laser[i].row;j<10;j++) {
safe[1][laser[i].col][j]=0;
safe[2][laser[i].col][j]=0;
safe[5][laser[i].col][j]=0;
safe[6][laser[i].col][j]=0;
}
for(j=laser[i].col;j>=0;j--) {
safe[2][j][laser[i].row]=0;
safe[3][j][laser[i].row]=0;
safe[6][j][laser[i].row]=0;
safe[7][j][laser[i].row]=0;
}
}
for(i=0;i<lavanum;i++) {
for(j=0;j<10;j++) {
safe[j][lava[i].col][row-1]=0;
}
}

this[lemming.col]=1;
for(i=0;i<row;i++) {
end=0;
for(j=0;j<col;j++)
next[j]=0;
next[0]=((this[0] || this[1]) && safe[i][0][i+1]);
next[col-1]=((this[col-1] || this[col-2]) && safe[i][col-1][i+1]);
for(j=1;j<col-1;j++)	{
next[j]=((this[j-1] || this[j] || this[j+1]) && safe[i][j][i+1]);
}
for(j=0;j<col;j++) {
end=(end || next[j]);
this[j]=next[j];
}
if ((end==0) || (safe[0][lemming.col][0]==0)) {
printf("GARRET\n");
end = 0;
break;
}
}

if (end)
printf("FERRET\n");

scanf("%s", size);
}
}
```