The Umbrella Problem: 2054

From Progteam

Revision as of 17:41, 22 May 2008 by Mlc413 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.



The Umbrella Problem: 2054
Problem Number 1301
Sorter: mlc413
Source: Unknown
Link: 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);
	}
}
 
Personal tools