题解 P2802 【回家】

AK_Automata · 2017-11-08 23:14:39 · 题解

发一篇dfs题解。

暴力dfs，枚举上下左右四个方向。

但是本题可以优化。

标记每个位置是否到过，到过了就不用再去了。

具体证明还希望哪位神犇证明一下。

对了，再给各位一个提示，也是我错的原因。

记住，1.枚举上下左右而不是左上等八个方位，我一开始就这样做，很愉快的40分。2.一个低级错误，把max打成了min，ans赋给了-1，但是居然还有70分，数据太水。。。。

代码：

#include <cmath>
#include <queue>
#include <deque>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//#include <bits/stdc++.h>
using namespace std;
const int oo=100005;
int n,m;
int map[15][15];//读入
bool flag[15][15];//标记
int ans=oo;//答案
void dfs(int i,int j,int k,int ansl){//i，j表示枚举到第i行第j列。k是当前体力，ansl是步数。
    if (i<1||j<1||map[i][j]==0||k==0||i>n||j>m||flag[i][j]==true) return ;//一大堆的判断。一个都不能少
    //cout<<i<<" "<<j<<" "<<k<<" "<<ansl<<endl;
    if (map[i][j]==3){ans=min(ans,ansl);return ;}//到家了
    if (map[i][j]==4)k=6;//恢复体力
    flag[i][j]=true;//走过
    dfs(i+1,j,k-1,ansl+1);
    dfs(i-1,j,k-1,ansl+1);
    dfs(i,j+1,k-1,ansl+1);
    dfs(i,j-1,k-1,ansl+1);
    flag[i][j]=false;//删除标记
    return ;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m;
int ii,jj;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
cin>>map[i][j]; 
if (map[i][j]==2) ii=i,jj=j;//标记起点，终点，不能误认为起点在第1行第1列。
}
memset(flag,false,sizeof(flag));//一开始都没走过。标记为false
dfs(ii,jj,6,0);
if (ans==oo) 
cout<<-1;
else
cout<<ans;//输出
return 0;
}