N*M的圖。
'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.
給出一張圖，和總共的步數。
然後輸出走過的圖，能走的地方都用*標記。
A了10來個小時，第一次用DFS做，標記visit[][],然後回溯，但是直接TLE。因為visit[][]標記的只是一次步數全部走完路徑，走完之後就都回溯了，這樣就造成很多重復的步驟。
第二次換了BFS，但是沒有用標記數組，直接爆棧了T_T。
第三次還是BFS，但是加了個visit[][]數組來儲存步數，在搜索的過程中，每次走到這一步，都更新visit[][]的步數，使得走到坐標（x,y）的剩余步數最大。
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
using namespace std;
char Map1[Max][Max];//原圖
char Map2[Max][Max];//輸出的圖
int visit[Max][Max];//儲存步數
int n,m;
int movex[4]= {1,-1,0,0};
int movey[4]= {0,0,1,-1};
struct kdq
{
int x,y,num;
};
int inmap(int x,int y)//判斷該點是否可以到達
{
if(x<=0||y<=0||x>n||y>m||Map1[x][y]=='#'||Map1[x][y]=='E'||Map1[x][y]=='Y')
return 0;
return 1;
}
int isEnemies(int x,int y)//判斷四個方向是否有E存在，有的話就停止。
{
int i,j;
for(i=0; i<4; i++)
{
int tx=x+movex[i];
int ty=y+movey[i];
if(inmap(tx,ty)&&Map1[tx][ty]=='E')
return 1;
}
return 0;
}
int movesum(int x,int y,int move)//計算走到這一步的步數，返回剩余步數。
{
int movenum,i;
if(Map1[x][y]=='T')
movenum=move-2;
if(Map1[x][y]=='R')
movenum=move-3;
if(Map1[x][y]=='.')
movenum=move-1;
if(Map1[x][y]=='P')
movenum=move-1;
for(i=0; i<4; i++)//判斷走到這一步後，四個方向上是否有E存在，有的話直接break;
{
int tx=x+movex[i];
int ty=y+movey[i];
if(tx>0&&ty>0&&tx<=n&&ty<=m&&Map1[tx][ty]=='E')
break;
}
if(i!=4)//i!=4,即是 break出來的，那麼證明這一點四個方向上有E存在，那麼則無法移動，即剩余步數為0。
{
if(movenum>0)
movenum=0;
}
return movenum;//返回步數
}
void bfs(int x,int y,int move)
{
kdq a;
int i,j;
for(i=0;i<=n;i++)//初始化visit[][]為無窮小
for(j=0;j<=m;j++)
visit[i][j]=-inf;
a.x=x;
a.y=y;
a.num=move;
queue<kdq>q;
q.push(a);
visit[x][y]=move;//初始的步數
int num=0;
while(!q.empty())
{
kdq temp=q.front();
q.pop();
if(temp.num==0)//如果步數為0，則不需要繼續下去，直接continue;
continue;
if(num)if(isEnemies(temp.x,temp.y))continue;//因為如果初始位置四個方向上有E的話，Y是可以移動的，所以用一個num來表示這一步是不是移動的第一步。
//如果不是第一步，並且四個方向上有E，則無法移動。continue;
num++;//標記是否是第一步的移動
for(int i=0;i<4;i++)
{
int tx=temp.x+movex[i];
int ty=temp.y+movey[i];
if(inmap(tx,ty))
{
kdq now;
now.num=movesum(tx,ty,temp.num);//計算剩余步驟
//if(Map1[tx][ty]=='P'&&now.num<1)continue;
if(now.num<0)continue;
if(now.num>visit[tx][ty])//更新visit[][]
{
visit[tx][ty]=now.num;
now.x=tx;
now.y=ty;
q.push(now);
if(Map1[tx][ty]!='P')
Map2[tx][ty]='*';//構造Map2[][]
}
}
}
}
}
int main()
{
int i,j,l,k,T,s;
int numx,numy;
cin>>T;
while(T--)
{
cin>>n>>m>>s;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
cin>>Map1[i][j];
Map2[i][j]=Map1[i][j];
if(Map1[i][j]=='Y')//找到初始坐標
{
numx=i;
numy=j;
}
}
}
bfs(numx,numy,s);
for(i=1;i<=n;i++)
{ www.2cto.com
for(j=1;j<=m;j++)
cout<<Map2[i][j];
cout<<endl;
}
cout<<endl;
}
return 0;
}
作者：kdqzzxxcc
