Description
HQM likes StarCraft very much, especially micro-controling. In a difficult micro-control map, he is requested to control 1 marine to defeat 2 zerglings. Although he is a very good player, he still has difficulty to pass the game. So he asks you to find a way to win the game.
The map is a 5*5 matrix, and every square is movable or unmovable. A unit, including the marine and the zergling, can only stay in a movable square. The 2 zerglings can be in the same square but at any time the marine can't stay in the same square with an undead zergling.
Both marine and zerglings have healthy point (we call it HP). When the game start, the marine's HP is m (1 <= m <= 16) and the zerlings' HP are both z (1 <= z <= 99).
The game may be regard as a round style game, in each round, the marine takes action first, and he can choose to move left, right, up or down. But the square he moves to must be movable and contain no alive zergling. The marine may also choose to attack, but in this condition the marine cannot move. He may choose an alive zergling and shoot at it, and every shoot will reduce the HP of the target by 1 (The marine cannot attack 2 zerglings even the two zergling are in the same square). If a zergling's HP less than 1, it will die. After the marine's action, all the alive zerglings will take action. If a zergling is in the square next to the marine's square, it will attack the marine, otherwise it will move follow the shortest way from its position to the marine's position. If there are many shortest ways, it will accord to the following order: left, up, right and down. If there is no way to reach marine, the zergling will not change its position. If the two zerglings are in the same square, their attacks will only reduce the marine's HP by 1,otherwise every zergling's attack will reduce the marine's HP by 1.
If after a round the zerglings are all killed, the player will win the game. But if the marine is killed or the marine can't kill the zerglings in 34 rounds (It is the Time Limit of the map), the player will lose. Now it's your job to determine whether the player can win or not. If he will win, how many rounds he will need at least?
Input
In the first 5 lines each contains 5 chars, referring to the map. '1' means the square is unmovable, other chars mean the square is movable, 'M' means the position of the marine, 'Z' and 'z' means the positions of two zerglings. The squares where the marine and zerglings stay at first are also movable. The sixth line of the input contains two integers m and z, refering to the HP of the marine and the zerglings.
Output
If the player can win the game, print "WIN" in the first line, and print the rounds needed at least in the second line, otherwise print "LOSE" in a single line.
Sample Input
zZ000
11110
00M10
01110
00000
15 15
Sample Output
WIN
30
http://poj.org/problem?id=2237
用BFS应该是可以的……
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int mapsize=5,maps=25,maxn=24;
const int len=4,maxrinhp=16,maxt=34;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
const int dn[5]={-1,-5,1,5,0};
bool atlas[mapsize+3][mapsize+3];
int g[maxn+3][maxn+3];
int bh[maxt+3][maxn+3][maxn+3][maxn+3][maxrinhp+3];
int marine,marinehp;
int zergling1,zergling2;
int zerglinghp;
int rj,zj1,zj2;
int hpmj,b;
char c;
struct val {
int marine_xy,zergling1_xy,zergling2_xy,marinehp,zerglinghp,dist;
#define m_xy marine_xy
#define z1_xy zergling1_xy
#define z2_xy zergling2_xy
#define m_hp marinehp
#define z_hp zerglinghp
void make_val(int m,int z1,int z2,int mhp,int zhp,int d) {
m_xy=m,z1_xy=z1,z2_xy=z2,m_hp=mhp,z_hp=zhp,dist=d;
}
}now;
queue<val> p;
inline int abs(int);
inline void getdata();
inline int getposid(int,int);
inline void floyd();
inline int zerglingmove(int);
inline int goby(int,int);
inline bool examine(val);
inline bool fastexamine(val);
inline void solve_DP();
inline void solve_BFS();
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve_BFS();
return 0;
}
inline int abs(int n) {
return (n>=0) ? n:-n;
}
inline void getdata() {
for (register int i=0;i<=len;i++)
for (register int j=0;j<=len;j++) {
cin>>c;
if (c!='1') atlas[i][j]=1; else atlas[i][j]=0;
if (c=='M') marine=getposid(i,j);
else if (c=='z') zergling1=getposid(i,j);
else if (c=='Z') zergling2=getposid(i,j);
}
cin>>marinehp>>zerglinghp;
}
inline int getposid(int x,int y) {
if (x<0 || x>=mapsize || y<0 || y>=mapsize) return -1;
return x*mapsize+y;
}
inline void floyd() {
memset(g,1,sizeof g);
for (register int i=0;i<=len;i++)
for (register int j=0;j<=len;j++)
if (atlas[i][j]) {
for (register int k=0;k<=3;k++)
if (atlas[i+dx[k]][j+dy[k]]) g[getposid(i,j)][getposid(i+dx[k],j+dy[k])]=1;
}
for (register int i=0;i<=maxn;i++) g[i][i]=0;
for (register int k=0;k<=maxn;k++)
for (register int i=0;i<=maxn;i++)
for (register int j=0;j<=maxn;j++)
if (g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j];
}
inline int zerglingmove(int d) {
for (register int i=0;i<=3;i++) {
int d1=d+dn[i];
if (d1>=0 && d1<maps)
if (g[d][d1]==1)
if (g[d][d1]+g[d1][rj]==g[d][rj]) return d1;
}
return d;
}
inline int goby(int d,int m) {
for (register int i=0;i<=3;i++) {
int d1=d+dn[i];
if (d1>=0 && d1<maps)
if (g[d][d1]==1)
if (g[d][d1]+g[d1][m]==g[d][m]) return d1;
}
return d;
}
inline bool examine(val state) {
while (state.z_hp>0) {
val newnode=state;
newnode.z_hp--;
if (state.m_hp<=0) return 0;
if (state.z_hp>zerglinghp) newnode.z1_xy=goby(state.z1_xy,state.m_xy);
if (newnode.z1_xy==state.m_xy) newnode.z1_xy=state.z1_xy,newnode.m_hp--;
newnode.z2_xy=goby(state.z2_xy,state.m_xy);
if (newnode.z2_xy==state.m_xy) newnode.z2_xy=state.z2_xy,newnode.m_hp--;
if (newnode.z2_xy==newnode.z1_xy && newnode.m_hp==state.m_hp-2) newnode.m_hp++;
state=newnode;
}
return 1;
}
inline bool fastexamine(val state) {
int z1min=1008,z1dt,z2min=1007,z2dt,z1hp=max(0,state.z_hp-zerglinghp),z2hp=min(zerglinghp,state.z_hp);
for (register int i=0;i<=3;i++) {
if (g[state.z1_xy][state.m_xy+dn[i]]<z1min) z1min=g[state.z1_xy][state.m_xy+dn[i]],z1dt=i;
if (g[state.z2_xy][state.m_xy+dn[i]]<z2min) z2min=g[state.z2_xy][state.m_xy+dn[i]],z2dt=i;
}
if (z1hp>0) {
z2min-=z1hp;
if (z1hp>z1min) state.m_hp-=z1hp-z1min;
}
if (z2min<0) {
if (z1dt!=z2dt) state.m_hp+=z2min;
else state.m_hp=state.m_hp+z2min+min(z1hp-z1min,abs(z2min));
}
if (z2hp<=state.m_hp) return 1;
return 0;
}
inline void solve_DP() {
getdata();
floyd();
memset(bh,1,sizeof bh);
bh[0][marine][zergling1][zergling2][marinehp]=zerglinghp*2;
bh[0][marine][zergling2][zergling1][marinehp]=zerglinghp*2;
for (register int t=0;t<=maxt;t++)
for (register int ri=0;ri<=maxn;ri++)
for (register int zi1=0;zi1<=maxn;zi1++)
for (register int zi2=0;zi2<=maxn;zi2++)
for (register int hpmi=1;hpmi<=marinehp;hpmi++)
if (bh[t][ri][zi1][zi2][hpmi]<1<<30) {
b=bh[t][ri][zi1][zi2][hpmi];
if (b<=0) {
cout<<"WIN"<<endl<<t<<endl;
return;
}
if (t+b>maxt) continue;
if (t<maxt) {
for (register int k=0;k<=4;k++) {
rj=ri+dn[k];
if (rj<0 || rj>maps) continue;
if (b>zerglinghp) if (rj==zi1) continue;
if (b>0) if (rj==zi2) continue;
if (g[ri][rj]>1) continue;
hpmj=hpmi;
if (k==4) b--;
if (b<=zerglinghp) zj1=zi1; else {
zj1=zerglingmove(zi1);
if (zj1==rj) hpmj--,zj1=zi1;
}
if (b<=0) zj2=zi2; else {
zj2=zerglingmove(zi2);
if (zj2==rj) hpmj--,zj2=zi2;
}
if (hpmj==hpmi-2) if (zj1==zj2) hpmj++;
if (hpmj>0) if (bh[t+1][rj][zj1][zj2][hpmj]>b) bh[t+1][rj][zj1][zj2][hpmj]=b;
}
}
}
cout<<"LOSE"<<endl;
}
inline void solve_BFS() {
getdata(),floyd();
if (zerglinghp>17) goto loop;
memset(bh,1,sizeof bh);
now.make_val(marine,zergling1,zergling2,marinehp,zerglinghp*2,0),p.push(now);
now.make_val(marine,zergling2,zergling1,marinehp,zerglinghp*2,0),p.push(now);
bh[0][marine][zergling1][zergling2][marinehp]=zerglinghp*2;
bh[0][marine][zergling2][zergling1][marinehp]=zerglinghp*2;
while (!p.empty()) {
now=p.front(),p.pop();
int b=now.z_hp,t=now.dist,ri=now.m_xy,zi1=now.z1_xy,zi2=now.z2_xy,hpmi=now.m_hp;
if (b<=0) {
cout<<"WIN"<<endl<<t<<endl;
return;
}
if (t+b>maxt) continue;
if (fastexamine(now)) {
cout<<"WIN"<<endl<<t+now.z_hp<<endl;
return;
}
if (t<maxt) {
for (register int k=0;k<=4;k++) {
rj=ri+dn[k];
if (rj<0 || rj>maps) continue;
if (b>zerglinghp) if (rj==zi1) continue;
if (b>0) if (rj==zi2) continue;
if (g[ri][rj]>1) continue;
hpmj=hpmi;
if (k==4) b--;
if (b<=zerglinghp) zj1=zi1; else {
zj1=zerglingmove(zi1);
if (zj1==rj) hpmj--,zj1=zi1;
}
if (b<=0) zj2=zi2; else {
zj2=zerglingmove(zi2);
if (zj2==rj) hpmj--,zj2=zi2;
}
if (hpmj==hpmi-2) if (zj1==zj2) hpmj++;
if (hpmj>0) if (bh[t+1][rj][zj1][zj2][hpmj]>b) {
val newnode;
newnode.make_val(rj,zj1,zj2,hpmj,b,t+1);
p.push(newnode);
bh[t+1][rj][zj1][zj2][hpmj]=b;
}
}
}
}
loop:cout<<"LOSE"<<endl;
}