首页 > 其他 > 详细

P1713 麦当劳叔叔的难题(90分)

时间:2019-09-10 23:52:57      阅读:45      评论:0      收藏:0      [点我收藏+]

标签:cout   叔叔   免费   爸爸   ace   pan   

题目描述

话说我们铭铭小朋友成功的回答了爸爸的问题,自然少不了要去索要些奖励,抠门的爸爸一看报纸,嘿,门口的麦当劳在搞活动,还有免费午餐哦,不过前提条件:得正确回答麦当劳叔叔的问题。

问题是这样描述的:

“我面前有很多个小朋友,我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的,我希望你帮我找出最聪明和最不聪明的小朋友,可能的最大的到达时间差。但是,小朋友只能按照一个特殊的规则前进。小朋友面前有一个n*n的格子矩阵,左下角的格子是起点,右上角的格子是大门。每个孩子每秒可以走向 上、下、左、右 前进一个格子,每个格子只能经过一次。但矩阵中间有一些障碍区,不能通过,只能绕过。”

例如,4*4的矩阵,格子(1, 1),(2, 3),(4, 2)为障碍区,黑格子就是一条可行的路线。时间为7。

输入格式

第1行为两个整数 n, m (2≤n≤10, 0≤m≤100)。

第2至第m+1行里,每行描述一个障碍区。用两个整数表示x, y (1≤x, y≤n)。

输出格式

仅1行,那个最大的时间差。

输入输出样例

输入 #1
4 3
1 1
2 3
4 2
输出 #1
4

玄学超时

开三个数组,记录当前步数f[][],最小步数d[][]以及最大步数u[][]


#include <bits/stdc++.h>
using namespace std;
int n,m,a[102][102],book[105][105],res=0x7ffffff,res1=-1;
int dfs(int now , int x , int y){
if( x > n || y > n || x < 1 || y < 1 || book[x][y] == 1){
return 0;
}
if( x == 1 && y == n ){
res=min(res,now);
res1=max(res1,now);
return 0;
}
book[x][y]=1;
dfs(now+1,x+1,y);dfs(now+1,x-1,y);dfs(now+1,x,y+1);dfs(now+1,x,y-1);
book[x][y]=0;return 0;
}
int main(){
int x , y ;
cin>>n>>m;
for (int i = 1 ; i <= m; i ++)cin>>x>>y,book[x][y]=1;
dfs(1,n,1);
cout<<res1-res;
return 0;
}

 

P1713 麦当劳叔叔的难题(90分)

标签:cout   叔叔   免费   爸爸   ace   pan   

原文:https://www.cnblogs.com/hrj1/p/11503862.html

(1)
(1)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号