题解 P2083 【找人】

AFOier · 2017-07-21 09:29:47 · 题解

dfs大水题，当然没有记录里其它dalao的方法跑得快，但是时限是1s，dfs完美AC。。。

#include <iostream>
#include <cmath>
using namespace std;
int n,m,v,zx,zy,ans;
struct house{int x,y;}a[1001][1001];
int dfs(int c,int f,int s,int zs)
{
    if(c==zx&&f==zy)return s; //如果到达终点，返回当前体力
    if(zs>n*m)return 10000000;//如果走的房间数大于所有的房间数但是还没有找到同学，说明有环，直接返回不可能（我用10000000代替impossible）
    dfs(a[c][f].x,a[c][f].y,s+v*(abs(a[c][f].x-c)),zs+1);//寻找当前房间的人所告诉的房间
}
int main()
{
    ans=10000000;
    cin>>n>>m>>v>>zx>>zy;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j].x>>a[i][j].y;//输入
    for(int i=1;i<=m;i++)
    ans=min(dfs(1,i,0,0),ans);//找最小的答案
    if(ans==10000000)cout<<"impossible"<<endl;//要是最小答案是10000000，说明肯定找不到那个同学，输出impossible
    else cout<<ans<<endl;//否则输出答案
}