題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=3345點選打開連結
War Chess
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2935 Accepted Submission(s): 736
Problem Description War chess is hh's favorite game:
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.
In the map:
'Y' is your current position (there is one and only one Y in the given map).
'.' is a normal grid. It costs you 1 MV to enter in this gird.
'T' is a tree. It costs you 2 MV to enter in this gird.
'R' is a river. It costs you 3 MV to enter in this gird.
'#' is an obstacle. You can never enter in this gird.
'E's are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with 'E', you will lose all your MV. Here “adjacent” means two grids share a common edge.
'P's are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on '.' . so ,it also costs you 1 MV to enter this grid.
Input The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T cases follow:
Each test case starts with a line contains three numbers N,M and MV (2<= N , M <=100,0<=MV<= 65536) which indicate the size of the map and Y's MV.Then a N*M two-dimensional array follows, which describe the whole map.
Output Output the N*M map, using '*'s to replace all the grids 'Y' can arrive (except the 'Y' grid itself). Output a blank line after each case.
Sample Input
5
3 3 100
...
.E.
..Y
5 6 4
......
....PR
..E.PY
...ETT
....TT
2 2 100
.E
EY
5 5 2
.....
..P..
.PYP.
..P..
.....
3 3 1
.E.
EYE
...
Sample Output
...
.E*
.*Y
...***
..**P*
..E*PY
...E**
....T*
.E
EY
..*..
.*P*.
*PYP*
.*P*.
..*..
.E.
EYE
.*.
Author shǎ崽
Source HDU2010省賽集訓隊選拔賽（校内賽）
Recommend lcy
這道題曾經打好久找不出錯 過了一個月之後又找 發現當碰到ER這種跟ET這種的時候寫錯
這道題挺麻煩 。。條件很多
碰到T兵力-2
R-3
E附近變為0
P不能停可以過
# E不能停不能過
然後要你輸出所有可以到的地方
得記憶化搜尋 不然會t
慢慢模拟 加油。。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<algorithm>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <queue>
#include <stack>
using namespace std;
int n,m,stepstep;
int book[1111][1111];
char mmap[1111][1111];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int xx;int yy=0;
struct xjy
{
int x;
int y;
int step;
bool operator < (const xjy &r)const
{
return step<r.step;
}
};
int judgeE(int x,int y)
{
if(mmap[x+1][y]=='E'||mmap[x-1][y]=='E'||mmap[x][y+1]=='E'||mmap[x][y-1]=='E')
return 1;
return 0;
}
void bfs()
{
priority_queue<xjy> q;
xjy mid;
mid.x=xx;mid.y=yy;mid.step=stepstep;
q.push(mid);
while(!q.empty())
{
mid=q.top();
q.pop();
xjy midmid;
midmid=mid;
//book[midmid.x][midmid.y]=midmid.step;
//printf("%d %d %d\n",mid.x,mid.y,mid.step);
if(mmap[mid.x][mid.y]!='P'&&mmap[mid.x][mid.y]!='Y')
{
mmap[mid.x][mid.y]='*';
}
if((mid.step>0&&book[mid.x][mid.y]<=mid.step))
{
for(int p=0;p<=3;p++)
{
midmid.x=mid.x+dir[p][0];
midmid.y=mid.y+dir[p][1];
if(mmap[midmid.x][midmid.y]=='#'||mmap[midmid.x][midmid.y]=='Y'||mmap[midmid.x][midmid.y]=='E'||book[midmid.x][midmid.y]>=midmid.step)
{
continue;
}
else if(midmid.x<=0||midmid.x>n||midmid.y<=0||midmid.y>m)
continue;
else if(mmap[midmid.x][midmid.y]=='R'&&midmid.step>=3)
{
if(judgeE(midmid.x,midmid.y))
{
int sstep=midmid.step;
midmid.step=0;
if(book[midmid.x][midmid.y]<midmid.step)
{
book[midmid.x][midmid.y]=0;
q.push(midmid);
}
midmid.step=sstep;
}
else if(book[midmid.x][midmid.y]<(midmid.step-3))
{
midmid.step-=3;
book[midmid.x][midmid.y]=midmid.step;
q.push(midmid);
midmid.step+=3;
}
else
continue;
}
else if(mmap[midmid.x][midmid.y]=='T'&&midmid.step>=2)
{
if(judgeE(midmid.x,midmid.y))
{
int sstep=midmid.step;
midmid.step=0;
if(book[midmid.x][midmid.y]<midmid.step)
{
book[midmid.x][midmid.y]=0;
q.push(midmid);
}
midmid.step=sstep;
}
else if(book[midmid.x][midmid.y]<(midmid.step-2))
{
midmid.step-=2;
book[midmid.x][midmid.y]=midmid.step;
q.push(midmid);
midmid.step+=2;
}
else
continue;
}
else if((mmap[midmid.x][midmid.y]=='P'||mmap[midmid.x][midmid.y]=='.'||mmap[midmid.x][midmid.y]=='*')&&midmid.step>=1)
{
if(judgeE(midmid.x,midmid.y))
{
int sstep=midmid.step;
midmid.step=0;
if(book[midmid.x][midmid.y]<midmid.step)
{
book[midmid.x][midmid.y]=0;
q.push(midmid);
}
midmid.step=sstep;
}
else if(book[midmid.x][midmid.y]<(midmid.step-1))
{
midmid.step-=1;
book[midmid.x][midmid.y]=midmid.step;
q.push(midmid);
midmid.step+=1;
}
else
continue;
}
}
}
}
}
int main()
{
int t=0;
scanf("%d",&t);
while(t--)
{
xx=yy=0;
memset(mmap,'#',sizeof(mmap));
memset(book,-1,sizeof(book));
scanf("%d%d%d",&n,&m,&stepstep);
getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%c",&mmap[i][j]);
if(mmap[i][j]=='Y')
{
xx=i;yy=j;
book[i][j]=stepstep;
}
}
getchar();
}
bfs();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%c",mmap[i][j]);
printf("\n");
}
}
}
![圖解elasticsearch的_source、_all、store和index[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)