P2083 找人

題目背景

無

題目描述

小明要到他的同學家玩，可他只知道他住在某一單元，卻不知住在哪個房間。那個單元有N層（1,2……N），每層有M（1,2……M）個房間。

小明會從第一層的某個房間開始找，他找的方式也很特別，每次到了一個房間，如果不是他的同學，他就會詢問這人，

然后他就會去那人告訴他的房間號，如果還不是，他就會繼續按這個方法找下去，直到找到。當然，他也有可能找不到同學。他的體力也是有限的，他每爬一層樓梯就會消耗V體力值。你的任務就是求找到同學耗費的最少體力值，如果找不到，就輸出impossible 。

輸入輸出格式

輸入格式：

?

共N+1行。

第一行，N，M，V，X，Y（X，Y表示同學只在X層Y房間）

2~N+1行，每行M*2個數字，第i+1行j*2-1個數Ak和j*2個數Ak+1表示住在i層j房間的人提供的信息是Ak層和Ak+1房間。（同學的信息就是自己的房間號）

?

輸出格式：

?

一個數，即答案。

?

輸入輸出樣例

輸入樣例#1：?復制 3 3 2 2 3 1 3 3 3 2 1 2 3 1 1 2 3 1 1 1 2 2 3 輸出樣例#1：?復制 2

說明

N<=1000，M<=100，V<=50

?

dfs、、、

zz啊、、由于本題是求最小值，因此在返回的時候不能返回-1！！！（才開始用-1判斷出現環的情況，老是掛、、）

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1010 #define maxn 1000000 using namespace std; int n,m,v,xx,yy,ans; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } struct Node {int x,y; }node[N][N]; int dfs(int x,int y,int s,int sum) {if(x==xx&&y==yy) return s;if(sum>n*m) return maxn;dfs(node[x][y].x,node[x][y].y,s+abs(node[x][y].x-x),sum+1); } int main() {ans=maxn;n=read(),m=read(),v=read(),xx=read(),yy=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)node[i][j].x=read(),node[i][j].y=read();for(int i=1;i<=m;i++) ans=min(ans,dfs(1,i,0,0));if(ans==maxn) printf("impossible");else printf("%d",ans*v);return 0; }

?

轉載于:https://www.cnblogs.com/z360/p/8231481.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的洛谷——P2083 找人的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。