poj 2110Mountain Walking解题报告

最近几天一直做二分，感觉有点上手，但是碰见新题还是迷茫，就比如这个，没想起来怎么去用二分枚举答案，看了别人的代码才知道的。唉，还是要多练习啊

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 105
 4 #define max(a,b) a>b?a:b
 5 #define minx(a,b) a<b?a:b
 6 int f[N][N];
 7 bool used[N][N];
 8 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 9 int n;
10 bool dfs(int down,int up,int x,int y)
11 {
12     int i;
13     if(x==n&&y==n)
14     return true;
15     int xt,yt;
16     for(i=0;i<4;i++)
17     {
18         xt=x+dir[i][0];
19         yt=y+dir[i][1];
20         if(xt>=1&&xt<=n&&yt>=1&&yt<=n&&!used[xt][yt]&&f[xt][yt]<=up&&f[xt][yt]>=down)
21         {
22             used[xt][yt]=true;
23             if(dfs(down,up,xt,yt))
24             return true;
25         }
26     }
27     return false;
28 }
29 int main()
30 {
31     int i,j,k,low,high,mid;
32     while(scanf("%d",&n)!=EOF)
33     {
34         low=130;
35         high=0;
36         for(i=1;i<=n;i++)
37         for(j=1;j<=n;j++)
38         {
39             scanf("%d",&f[i][j]);
40         }
41         high=120;
42         low=0;
43         int ans=120;
44         while(low<=high)
45         {
46             mid=(low+high)>>1;
47             int min=max(f[1][1]-mid,0);
48             int flag=0;
49             for(i=f[1][1]-mid;i<=f[1][1];i++)
50             {
51                 memset(used,0,sizeof(used));
52                 used[1][1]=true;
53                 if(dfs(i,i+mid,1,1))
54                 {
55                     flag=1;
56                     break;
57                 }
58             }
59             if(flag)
60             {
61                 ans=minx(mid,ans);
62                 high=mid-1;
63             }
64             else
65             low=mid+1;
66         }
67         printf("%d\n",ans);
68     }
69     return 0;
70 }