http://acm.hdu.edu.cn/showproblem.php?pid=1072
#include<iostream>
#include<queue>
using namespace std;
struct Node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int vi,vj;
int time;//剩余时间
int step;//花费时间
};
int gra[9][9];
int mark[9][9];//走到i、j所剩余的时间
int m,n,mins;
int si,sj,ei,ej;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dir[4][2]= {-1,0,1,0,0,-1,0,1};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int k;
Node p,q;
queue<Node>Q;
p.step = 0;
p.time = 6;
p.vi = si;
p.vj = sj;
Q.push(p);
mark[si][sj] = p.time;
while(!Q.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
q = Q.front();
Q.pop();
if(q.vi == ei && q.vj == ej)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(q.time > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {//跑掉
mins = q.step;
return ;
}
else
continue;
}
if(gra[q.vi][q.vj] == 4) //时间重置
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mark[q.vi][q.vj] = 6;
q.time = 6;
}
for(k=0;k<4;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p.vi = q.vi + dir[k][0];
p.vj = q.vj + dir[k][1];
p.time = q.time - 1;
p.step = q.step + 1;
if(p.vi>=0 && p.vi<m && p.vj>=0 && p.vj<n && gra[p.vi][p.vj]!=0 && q.time > 0
&& mark[p.vi][p.vj] < p.time)//不超界又不是墙
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mark[p.vi][p.vj] = p.time;
Q.push(p);
}
}//for(k=0;k<4;k++)
}//while(!Q.empty())
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t;
cin>>t;
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
cin>>m>>n;
int i,j;
for(i=0;i<m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=0;j<n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
cin>>gra[i][j];
if(gra[i][j] == 2)//起点
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
si = i;
sj = j;
}
else if(gra[i][j] == 3)//终点
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ei = i;
ej = j;
}
mark[i][j] = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
mins = 1000;
bfs();
if(mins != 1000) //逃掉
cout<<mins<<endl;
else
cout<<-1<<endl;
}
return 0;
}
|