Shortest path of the king（CodeForces - 3A）

ゝ一世哀愁。 2022-01-23 19:57 169阅读 0赞

The king is left alone on the chessboard. In spite of this loneliness, he doesn’t lose heart, because he has business of national importance. For example, he has to pay an official visit to square t. As the king is not in habit of wasting his time, he wants to get from his current position s to square t in the least number of moves. Help him to do this.

In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).

![在这里插入图片描述][20190531162715294.png]  
**Input**  
he first line contains the chessboard coordinates of square s, the second line — of square t.  
Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1 to 8.

**Output**  
In the first line print n — minimum number of the king’s moves. Then in n lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD.  
L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.

Examples

**Input**  
a8  
h1

**Output**  
7  
RD  
RD  
RD  
RD  
RD  
RD  
RD

题意：给你两个点，从第一个点到第二个点的最短路径（一共8个方向）。

思路：先走个正方形也就是先走对角，两个坐标的横坐标差和纵坐标差的最小值。此时横坐标或者纵坐标至少一个坐标是相同的。  
然后再走直线走到最后就行了。（代码虽然长，但是很好理解）

AC代码：

/**
     *　　┏┓　　　┏┓+ +
     *　┏┛┻━━━┛┻┓ + +
     *　┃　　　　　　　┃ 　
     *　┃　　　━　　　┃ ++ + + +
     * ████━████ ┃+
     *　┃　　　　　　　┃ +
     *　┃　　　┻　　　┃
     *　┃　　　　　　　┃ + +
     *　┗━┓　　　┏━┛
     *　　　┃　　　┃　　　　　　　　　　　
     *　　　┃　　　┃ + + + +
     *　　　┃　　　┃
     *　　　┃　　　┃ +  神兽保佑
     *　　　┃　　　┃    代码无bug　　
     *　　　┃　　　┃　　+　　　　　　　　　
     *　　　┃　 　　┗━━━┓ + +
     *　　　┃ 　　　　　　　┣┓
     *　　　┃ 　　　　　　　┏┛
     *　　　┗┓┓┏━┳┓┏┛ + + + +
     *　　　　┃┫┫　┃┫┫
     *　　　　┗┻┛　┗┻┛+ + + +
     */
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<map>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int mmax=1e6+10;
    string nn;
    int main()
    {
    	map<char,int> s;
    	s['a']=1;
    	s['b']=2;
    	s['c']=3;
    	s['d']=4;
    	s['e']=5;
    	s['f']=6;
    	s['g']=7;
    	s['h']=8;
    	string a1,a2;
    	int b1,b2;
    	string s1,s2;
    	while(cin>>s1) 
    	{
    		cin>>s2;
    		ll a1=s[s1[0]];
    		ll a2=s[s2[0]];
    		b1=s1[1]-'0';
    		b2=s2[1]-'0';
    		ll len=0,k=0;
    		len=min(fabs(a1-a2),fabs(b1-b2));
    //		cout<<len<<endl;
    //		cout<<a1<<" "<<b1<<endl;
    //		cout<<a2<<" "<<b2<<endl;
    		if(a1<a2&&b1>b2)
    		{
    			//cout<<"121455"<<endl;
    			nn="RD";
    			//cout<<"RD"<<endl;
    			a1+=len;
    			b1-=len; 
    		}
    		if(a1<a2&&b1<b2)
    		{
    			nn="RU";
    			//cout<<"RU"<<endl;
    			a1+=len;
    			b1+=len;
    		}
    		if(a1>a2&&b1<b2)
    		{
    			nn="LU";
    			//cout<<"LU"<<endl;
    			a1-=len;
    			b1+=len;
    		}	
    		if(a1>a2&&b1>b2)
    		{
    			nn="LD";
    			//cout<<"LU"<<endl;
    			a1-=len;
    			b1-=len;
    		}	
    		//cout<<a1<<" "<<b1<<endl;
    		//cout<<nn<<endl;
    		if(a1==a2&&b1==b2)
    		{
    			cout<<len<<endl;
    			for(int i=1;i<=len;i++)
    				cout<<nn<<endl;
    		}
    		if(a1==a2&&b1>b2)  //往下走 
    		{
    			cout<<len+b1-b2<<endl;
    			for(int i=1;i<=len;i++)
    			{
    				cout<<nn<<endl;
    			}
    			for(int i=1;i<=b1-b2;i++)
    			{
    				cout<<"D"<<endl;
    			}
    		}
    		if(a1<a2&&b1==b2)//往右走
    		{
    			cout<<len+a2-a1<<endl;
    			for(int i=1;i<=len;i++)
    			{
    				cout<<nn<<endl;
    			}
    			for(int i=1;i<=a2-a1;i++)
    			{
    				cout<<"R"<<endl;
    			}
    		}
    		if(a1==a2&&b1<b2)//往上走
    		{
    			cout<<len+b2-b1<<endl;
    			for(int i=1;i<=len;i++)
    			{
    				cout<<nn<<endl;
    			}
    			for(int i=1;i<=b2-b1;i++)
    			{
    				cout<<"U"<<endl;
    			}
    		}
    		if(a1>a2&&b1==b2) //往左走 
    		{
    			cout<<len+a1-a2<<endl;
    			for(int i=1;i<=len;i++)
    			{
    				cout<<nn<<endl;
    			}
    			for(int i=1;i<=a1-a2;i++)
    			{
    				cout<<"L"<<endl;
    			}
    		}
    		
    	}
    	return 0;
    }

还有一个类似的题：“华为杯”山东理工大学第十一届ACM程序设计竞赛（热身赛）  
D题 ： 小鑫鑫的沙漠之旅

**Problem Description**

在一个非常大的沙漠里，这个沙漠是一个二维平面。

小鑫鑫同学在沙漠中迷失了方向，他每天只能往上，下，左，右四个方向移动一个单位的距离。

他为了摆脱他在大沙漠中无聊的心情，奇数天他会自己选择方向移动，偶数天他会按照上一天移动的方向顺时针旋转 90° 的方向移动，第一次移动是第一天。

聪明的你们知道小鑫鑫的起始位置为 (x1, y1)，他所要到达的目的地是 (x2, y2)。聪明的你能告诉他，他最少需要几天才能逃离这个沙漠吗？

**Input**

输入一个 T，总共有 T 组测试数据。

每组数据输入四个用空格隔开的整数：x1, y1, x2, y2。

(-1e9 <= x1, y1, x2, y2 <= 1e9 ，T<=50)

**Output**

输出从 (x1, y1) 到 (x2, y2) 所需的最小天数。

**Sample Input**

3  
0 0 0 1  
0 0 1 1  
0 0 0 2

**Sample Input**  
1  
2  
4

题解：还是先走一个正方形，这样最短，正方形的边长 \* 2，此时横坐标或者纵坐标至少一个坐标是相同的。  
走直线，  
1.注意如果是一个偶数的话，剩下的路程 \* 2 ，加入往上走2个格，先往上走一个格，偶数天向右走，第三天往左走，第四天就到了，就是路程是偶数每次都走一个T字，一共走路程\*2步。  
2.路程是奇数就好办了，把最后的一个路程拿出来不就是路径是偶数了，最后的一步只需一步就走完了，所以是（n-1）\*2

AC代码：

[20190531162715294.png]: /images/20220124/01c55242969b4e8fa6571fab2b6ea499.png