poj 1878 Jill's Bike (广搜)

太过爱你忘了你带给我的痛 2022-03-27 09:46 146阅读 0赞

<table style="font-family:Simsun"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      Jill's Bike 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td colspan="3"><strong>Memory Limit:</strong>&nbsp;30000K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;1263</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;326</td> 
        <td>&nbsp;</td> 
        <td style="font-weight:bold; color:red">Special Judge</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Description</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Jill Bates hates climbing hills. Jill rides a bicycle everywhere she goes, but she always wants to go the easiest and shortest way possible. The good news is that she lives in Greenhills, which has all its roads laid out in a strictly rectangular grid--east-west roads are streets; north-south roads are avenues and the distance between any two adjacent grid points is the same. The bad news is that Greenhills is very hilly and has many one-way roads.&nbsp; 
     <br> In choosing a route between where she starts and where she ends, Jill has three rules:&nbsp; 
     <br> 
     <ol> 
      <li>Avoid any climb of more than 10 meters between adjacent grid points.&nbsp;<br> </li> 
      <li>Never go the wrong way on a one-way road.&nbsp;<br> </li> 
      <li>Always travel the shortest possible route.</li> 
     </ol> 
     <br> Your program should help Jill find an acceptable route.&nbsp; 
     <br> 
     <br> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Input</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      The input contains data for several maps in the following form:&nbsp; 
     <br> 
     <ul> 
      <li>The first line contains two integers, separated by one or more spaces. The first integer n represents the number of streets, and the second integer m represents the number of avenues, 1&lt;= n &lt;=20, 1&lt;= m &lt;=20.&nbsp;<br> </li> 
      <li>The next n lines contain the altitudes of grid points. Each line represents a street and contains a sequence of m integers separated by one or more spaces. These integers represent the altitude in meters of the grid points along that street. Even if a particular street and avenue have no intersection, the altitude is still given for that grid point.&nbsp;<br> </li> 
      <li>One or more lines follow that define the one-way roads. Each road is represented by two pairs of integers, separated by one or more spaces, in the form:&nbsp;<br> 
       <blockquote> 
        <em>street avenue street avenue</em> 
       </blockquote> <br> The first street and avenue define the starting point of the road and the second pair define the ending point. Since Greenhills is a strict grid, if the two points are not adjacent in the grid, the road passes through all the intervening grid points. For example,&nbsp;<br> 
       <blockquote> 
        <code>5 7 5 8&nbsp;<br> 5 8 5 9&nbsp;<br> 5 9 5 10</code> 
       </blockquote> <br> represents roads 5-7 to 5-8, 5-8 to 5-9, and 5-9 to 5-10. Road definitions are terminated by a line containing four zeroes in the above format.&nbsp;<br> </li> 
      <li>Finally, one or more lines will follow that contain pairs of grid points between which Jill wants to find an optimal path, in the form:&nbsp;<br> 
       <blockquote> 
        <em>street avenue street avenue</em> 
       </blockquote> <br> As before, the integer pairs are separated by one or more spaces. The end of the input set is defined by a line containing four zeroes, formatted as before.</li> 
     </ul> 
     <br> You may assume that all street and avenue numbers are within the bounds defined by the first line of input, and that all road definitions are strictly north-south or east-west.&nbsp; 
     <br> 
     <br> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Output</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      For each path query in the input, output a sequence of grid points , from the starting grid point to the ending grid point, which meets Jill's three rules. Output grid points as 'street-avenue' separated by the word 'to'. If there is more than one path that meets Jill's criteria, any such path will be acceptable. If no route satisfies all the criteria, or if the starting and ending grid points are the same, output an appropriate message to that effect. Output a blank line between each output set. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Input</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">3 4
10 15 20 25
19 30 35 30
10 19 26 20
1 1 1 4
2 1 2 4
3 4 3 3
3 3 1 3
1 4 3 4
2 4 2 1
1 1 2 1
0 0 0 0
1 1 2 2
2 3 2 3
2 2 1 1
0 0 0 0
</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Output</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2

To get from 2-3 to 2-3, stay put!

There is no acceptable route from 2-2 to 1-1.
</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Hint</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <img src="http://poj.org/images/1878_1.jpg" alt=""> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Source</p> </td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][]\] \[Go Back\] \[[Status][]\] \[[Discuss][]\]

直接上代码：

#include <iostream>
    using namespace std;
    
    const int ds[4]={-1,0,0,1};
    const int da[4]={0,1,-1,0};
    struct State
    {
        int s,a; //(s,a)为网格的行列坐标
    };
    int n,m;
    int alt[20][20];  //海拔高度
    int s1,a1,s2,a2;//当前单项路起点和终点的坐标
    int ss,as,se,ae;  //jill起点和终点的坐标
    int isd[20][20][4];//是否有通向d方向的路
    int par[20][20];//标记到达网格点的方向
    State qu[400];//duilie
    int qs,qt;
    
    void Bfs();
    void Print(int ss,int as,int se,int ae);
    int Getdirection(); //求得当前单向路线的方向索引
    
    int main()
    {
        int d,i,j;
        while(cin >> n >>m)
        {
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                {
                    cin >> alt[i][j];
                    isd[i][j][0]=isd[i][j][1]=isd[i][j][2]=isd[i][j][3]=0;
                }
            }
            while(cin >> s1 >> a1 >> s2 >>a2)
            {
                if(s1==0 && s2==0 && a1==0 && a2==0) break;
                s1--; a1--; s2--; a2--;
                d=Getdirection();
                while(s1!=s2 || a1!=a2)
                {
                    isd[s1][a1][d]=1;
                    s1+=ds[d]; a1+=da[d];
                }
            }
            while(cin >> ss >> as >> se >> ae)
            {
                if(ss==0 && as==0 && se==0 && ae==0)
                break;
                ss--; as--; se--; ae--;
                if(ss==se && as==ae)
                {
                    cout<<"To get from "<<ss+1<<"-"<<as+1<<" to "<<se+1
                        <<"-"<<ae+1<<", stay put! ";
                }
                else
                {
                    for(i=0;i<n;i++)
                    {
                        for(j=0;j<m;j++)
                        par[i][j]=-1;
                    }
                    Bfs();
                    if(par[se][ae]==-1)
                    cout<<"There is no acceptable route from "<<ss+1<<"-"
                        <<as+1<<" to "<<se+1<<"-"<<ae+1<<".";
                    else
                    Print(ss,as,se,ae);
                }
                cout<<"\n\n";
            }
        }
        return 0;
    }
    void Bfs()
    {
        int i;
        qu[0].s=ss; qu[0].a=as;
        qs=0;qt=1;
        while(qs<qt)
        {
            for(i=0;i<4;i++)
            {
                int cs=qu[qs].s+ds[i];
                int ca=qu[qs].a+da[i];
                if(cs<0||cs>=n||ca<0||ca>=m) continue;
                if(par[cs][ca]!=-1||isd[qu[qs].s][qu[qs].a][i]==0
                   ||alt[cs][ca]-alt[qu[qs].s][qu[qs].a]>10) continue;
                par[cs][ca]=i;
                qu[qt].s=cs; qu[qt].a=ca; qt++;
            }
            qs++;
        }
    }
    void Print(int ss,int as,int se,int ae)
    {
        if(ss!=se||as!=ae)
        {
            int cd=par[se][ae];
            Print(ss,as,se-ds[cd],ae-da[cd]);
            cout<<" to ";
        }
        cout << se+1 <<"-" << ae+1;
    }
    int Getdirection()
    {
        if(s1==s2)
        {
            if(a1<a2) return 1;
            else return 2;
        }
        else
        {
            if(s1<s2) return 3;
            else return 0;
        }
    }

[Submit]: http://poj.org/submit?problem_id=1878
[Status]: http://poj.org/problemstatus?problem_id=1878
[Discuss]: http://poj.org/bbs?problem_id=1878