自动搬运

查看原文

来自洛谷，原作者为

	AFOier **

搬运于2025-08-24 21:33:48，当前版本为作者最后更新于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;//否则输出答案
}