哈利被困在了一个魔法花园里。魔法花园是一个 N*M 的矩形，在其中有着许多植物，
这些植物会在时刻 K 的倍数消失。 哈利每单位时间都会选择上、下、左、右四
个方向的其中一个进行移动。
#include<iostream>
using namespace std;
int n,m,k;
#define max 100
char mmap[max][max];
int mmin;
#define MIN(a,b) ((a)<(b)?(a):(b));
int x1,x2,y1,y2;
int mmde[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int visited[max][max];
int step;
int sum;
void dfs(int x,int y){ int i;
int mx,my;
if(mmap[x][y]=='3'){
mmin=MIN(step,mmin); }
else
// if(mmap[x][y]!='1'||(step%k==0&&mmap[x][y]=='1'))
{
int no=0;
for(i=0;i<4;i++){
mx=x+mmde[i][0];
my=y+mmde[i][1];
// cout<<"pre:"<<endl<<" x: "<<mx<<" y: "<<my<<" step: "<<step<<endl;
if(
(
(mmap[mx][my]!='1'&&!visited[mx][my]&&mx>=1&&mx<=n&&my>=1&&my<=m)
||
(
(step+1)%k==0&&mmap[mx][my]=='1'
)
)
&&
(
abs(mx-x2)+abs(my-y2)+step<mmin
)
){
step++;
sum++;
visited[mx][my]=1;
dfs(mx,my);
visited[mx][my]=0;
step--; }
else no++;
/*
else if(abs(mx-x2)+abs(my-y2)+sum>mmin){
cout<<"too long"<<endl; }
else
{
cout<<"weizhishoxian"<<endl; } */
}
//重复走 样例3
if(no==4){
for(i=0;i<4;i++){
mx=x+mmde[i][0];
my=y+mmde[i][1];
if(mmap[mx][my]=='0'||mmap[mx][my]=='2'){
// cout<<"visited---mmap["<<mx<<"]["<<my<<"] to 0"<<endl;
visited[mx][my]=0;} }
for(i=0;i<4;i++){
mx=x+mmde[i][0];
my=y+mmde[i][1];
if(
(
(mmap[mx][my]!='1'&&!visited[mx][my]&&mx>=1&&mx<=n&&my>=1&&my<=m)
||
(
(step+1)%k==0&&mmap[mx][my]=='1'
)
)
&&
(
abs(mx-x2)+abs(my-y2)+step<mmin
)
){
step++;
sum++;
visited[mx][my]=1;
dfs(mx,my);
visited[mx][my]=0;
step--; }
}
} }
}
int main(){
//scanf("%d%d%d",&n,&m,&k);
int icase;
cin>>icase;
while(icase--){
cin>>n>>m>>k;
int i,j;
memset(visited,0,sizeof(visited));
mmin=1000000;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>mmap[i][j];
if(mmap[i][j]=='2')
{x1=i;y1=j;}
else if(mmap[i][j]=='3')
{x2=i;y2=j;}
}
}
visited[x1][y1]=1;
// cout<<"now:x1:"<<x1<<" y1:"<<y1<<endl;
step=0;
sum=0;
dfs(x1,y1);
if(mmin==1000000)cout<<"Mobiliarbus"<<endl;
else cout<<mmin<<endl;
// cout<<"sum:"<<sum<<endl;
}
}
/*
100
6 6 2
000200
000100
010000
000100
000100
001310
7
6 6 2
000300
000100
010000
000100
000100
001210
Mobiliarbus
3 5 3
00102
00011
00300
6
3 5 3
00002
00111
00300
4
&&(abs(mx-x2)+abs(my-y2)+step<=mmin))剪枝
*/
版权声明：本文为博主原创文章，未经博主允许不得转载。