Nightmare
这道题目，本来我以为就是搜索题嘛，就直接写起来了DFS，但是试过几次之后发现WA个不停。然后我终于明白了DFS和BFS的区别。在这道题目的讨论区里都是用BFS写的，我就试着写了个BFS。结果直接AC了。。通过这个我感觉大致是这么个情况：当搜索最短路径的时候最好要选用BFS，当检查是否能走出去的时候选用DFS。用DFS求最短路径貌似不是每次都是最优解。它只保证能找到。当然了，这是我的愚见了。
这题的要点：
- 每一个能走的点都能都很多次，而不是只能走一次。
- 标记为4的点，是重置装置，虽然题目说该重置装置可以被使用多次，但这完全是误导罢了，如果你真的多次使用的话，那么你的程序一定会陷入死循环的。你说是不？所以，在你访问过一遍之后再去访问第二遍是没有任何意义的。因为接下来你要经历的状态，前面一定一定经历过喽，再走就会死循环，所以做个标记，走过就不要再走了。
这里我没有定义一个类来保存坐标。我是使用了一个简单的数学方法，我声明的一个对象是 queue<int> q。那么我是怎么用一个整型来保存二维坐标的呢？实际很简单
i*10+j 因为i，j都是个位数，所以很容易还原哦。
#include <iostream>
#include <queue>
using namespace std;
int n,m,si,sj,mini;
int ma[9][9];
int rest[9][9];
int step[9][9];
int dir[4][2]={0,1,0,-1,-1,0,1,0};
queue<int> q;
void bfs(int i,int j)
{
q.push(i*10+j);
while(!q.empty())
{
int front=q.front();
q.pop();
i = front/10;
j = front%10;
if(!rest[i][j])
continue ;
if(ma[i][j]==3)
{
if(mini==-1||mini>step[i][j])
mini=step[i][j];
continue ;
}
else if(ma[i][j]==4)
{
rest[i][j]=6;
ma[i][j]=0;
}
for(int k=0;k<4;k++)
{
int x=i+dir[k][0];
int y=j+dir[k][1];
if(x<0||x>=n||y<0||y>=m||!ma[x][y]||rest[x][y]>=rest[i][j])
continue;
rest[x][y] = rest[i][j]-1;
step[x][y] = step[i][j]+1;
q.push(x*10+y);
}
}
return ;
}
int main()
{//freopen("in.txt","r",stdin);
int t;
cin>>t;
while(t--)
{
mini=-1;
cin>>n>>m;
memset(ma,0,sizeof ma);
memset(rest,0 ,sizeof rest);
memset(step,0 ,sizeof step);
for(int i = 0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>ma[i][j];
if(ma[i][j]==2)
{
si=i;
sj=j;
}
}
ma[si][sj] = 0;
rest[si][sj] = 6;
bfs(si,sj);
cout<<mini<<endl;
}
return 0;
}