Problem Statement
You are playing a game titled Resident Slime. You will play the role of the hero and exterminate undead slimes.
You are on a level that is represented by an RxC rectangular grid of cells given in String[] field. Rows are numbered 0 through R-1 from top to bottom, and columns are numbered 0 through C-1 from left to right. field[r][c] represents the content of the cell located at row r and column c and is one of the following:
- '.' : an empty cell.
- '#' : a wall.
- '$' : an empty cell where you initially reside.
- '1'-'9' : a stationary undead slime whose regenerative power is equal to the digit representing it.
You are going to exterminate all the slimes in this level. Unfortunately, after each slime is killed, it only stays dead for a limited time before it gets revived. Your goal is to get the level into a state where every slime is dead. At that point, they will no longer come back to life. More specifically, the game works as follows.
- You start at the cell denoted by '$'.
- At the beginning of each turn, you either wait or move to one of the four adjacent cells (those which share a side with your current location). You cannot move to a cell which contains a wall.
- Next, if there's a dead slime in your new location, it will get revived.
- Next, if your new location is occupied by an undead slime, that slime gets killed. The killed slime will remain in the cell.
- Next, each slime is revived if its regenerative power is equal to the number of turns ago it was last killed.
- Finally, if at this moment all undead slimes are killed, you win the level. Otherwise, the turn advances and the game continues.
Pre-requisite
- BFS (Breadth First Search): Since the distance between cells is 1 unit, we can find single source shortest path using BFS.
- Trying out all permutation using backtracking method.
- Scope reduction by understanding the problem and the constraint.
Code
public class SlimeXResidentSlime {
final int INF = Integer.MAX_VALUE / 3;
int R, C, N;
String[] _field;
int[] x,y,t;
int[][] path;
int[][] dist;
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
boolean valid(int x,int y)
{
if(x < 0 || x >= R || y < 0 || y >= C)
return false;
if(_field[x].charAt(y) == '#') return false;
return true;
}
void bfs(int sx, int sy)
{
int[] Q = new int[123456];
for(int i = 0 ; i < R; i ++)
Arrays.fill(path[i], INF);
int hx, tx;
hx = tx = 0;
Q[tx++] = sx;
Q[tx++] = sy;
path[sx][sy] = 0;
while(hx < tx)
{
int headx, heady;
headx = Q[hx++];
heady = Q[hx++];
for(int i = 0 ; i < 4; i ++)
{
int auxx, auxy;
auxx = headx + dx[i];
auxy = heady + dy[i];
if(valid(auxx, auxy) && path[auxx][auxy] == INF)
{
path[auxx][auxy] = path[headx][heady] + 1;
Q[tx++] = auxx;
Q[tx++] = auxy;
}
}
}
}
public int exterminate(String[] field) {
/* Global Variables */
R = field.length;
C = field[0].length();
_field = field;
N = 0;
x = new int[10]; y = new int[10]; t = new int[10];
for(int i = 0 ; i < R; i ++)
for(int j = 0 ; j < C ; j++)
if(field[i].charAt(j) > '0' && field[i].charAt(j) <= '9')
{
x[N] = i;
y[N] = j;
t[N] = field[i].charAt(j) - '0';
N++;
if(N > 9)
return -1;
}
for(int i = 0 ; i < R ; i ++)
for(int j = 0 ; j < C ;j ++)
if(field[i].charAt(j) == '$')
{
x[N] = i; y[N] = j;
break;
}
dist = new int[N+1][N+1];
path = new int[R][C];
for(int i = 0 ; i <= N ; i ++) {
bfs(x[i], y[i]);
for (int j = 0; j <= N; j++) {
dist[i][j] = path[x[j]][y[j]];
}
}
boolean[] used = new boolean[N];
int res = INF;
for(int i = 0; i < N; i ++)
{
used[i] = true;
int timeRem = dist[N][i];
for(int j = 0; j <= Math.min(8, t[i] - 1) ; j++)
{
if(dfs(0, i, j, used))
{
timeRem += j;
res = Math.min(res, timeRem);
break;
}
}
used[i] = false;
}
return (res == INF) ? -1 : res;
}
private boolean dfs(int x, int prev, int time, boolean[] used) {
if(time < 0)
return false;
if(x == N - 1) return true;
boolean res = false;
for(int i = 0; i < N; i++)
{
if(used[i]) continue;
used[i] = true;
res |= dfs(x+1, i, Math.min(time - dist[i][prev], t[i]-1), used);
used[i] = false;
}
return res;
}
}