UESTC 758-P酱的冒险旅途【BFS】

短命女 2022-08-20 15:28 67阅读 0赞

# P酱的冒险旅途 #

[Edit][]

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

SubmitStatus

P酱是个可爱的男孩子，有一天他在野外冒险，不知不觉中走入了一块神奇的地方。他在0 时刻进入这个地方，每一时刻他都只能向某一特定的方向移动长度为1的距离，当然他也可以选择不移动。移动需要花费1 的时间。

各个时刻他允许移动的方向由一个字符串给出，字符串只包含`U`、`D`、`L`、`R`四种字符，其中`U`表示向上（y 轴正方向）移动，`D`表示向下（y 轴负方向）移动，`L`表示向左（x 轴负方向）移动，`R`表示向右（x 轴正方向）移动。

字符串的第x 个字符代表了第x 时刻P酱可以移动的方向，字符串的长度只有t ，也就是说，超过t 时刻，P酱就要被邪恶的魔王大爷抓走了~

现在P酱在坐标原点，即(0,0) 点，而出口在(x,y) 点，P酱希望在规定的时间t 内尽快走到出口。帮助P酱在最短的时间内离开这里吧~

## Input ##

第一行包含一个正数 T (T≤100 )，表示数据组数。

接下来每组数据包含两行，第一行包含三个整数 x,y,t (−10 5 ≤x,y≤10 5 ,0<t≤10 5 )；第二行包含一个长度为t 的字符串，第i 个字符表示在i 时刻他能移动的方向，字符串只包含`U`，`D`，`L`，`R`四种字母。

## Output ##

对于每组数据输出一行，表示P酱到达出口的最早时刻。如果他无法在t 时刻内到达出口，输出`-1`。

## Sample input and output ##

<table> 
 <thead> 
  <tr> 
   <th>Sample Input</th> 
   <th>Sample Output</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td> <pre><code>2
1 -1 5
LDRDR
-2 1 8
RRUDDLRU</code></pre> </td> 
   <td> <pre><code>3
-1</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

## Hint ##

第一组样例：

1.  P酱在0 时刻位于原点(0,0) ，他只能向左移动，但他选择不走。
2.  P酱在1 时刻依然位于原点(0,0) ，他只能向下移动，于是他向下移动到了(0,−1)
3.  P酱在2 时刻位于(0,−1) ，他只能向右移动，于是他移动到了出口(1,−1) ，所以在3 时刻，P酱离开了这片区域！

## Source ##

第五届ACM趣味程序设计竞赛第二场（正式赛）

#include<stdio.h>
    #include<cmath>
    #include<queue>
    #include<string.h>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    char map[100000];
    int T,ex,ey,t;
    struct node
    {
    	int x,y,step;
    	int zuo;
    };
    queue<node> q;
    bool ff;
    int ans;
    
    double ji(int x1,int y1,int x2,int y2)
    {
    	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    
    //int biao;
    void wc()
    {
    	while(!q.empty())
    	{
    		node end;
    		end=q.front();
    		q.pop();
    		if(end.x==ex&&end.y==ey)
    		{
    			ff=true;
    			ans=min(ans,end.step);
    			printf("%d\n",ans);
    			return ;
    		}
    		if(end.step>t)
    		{
    			continue;
    		}
    		end.step++;
    		end.zuo++;
    		if(map[end.zuo]=='U')
    		{
    			node end2=end;
    			end2.x=end.x+0;
    			end2.y=end.y+1;
    			end2.zuo=end.zuo;
    			if(ji(end2.x,end2.y,ex,ey)<ji(end.x,end.y,ex,ey))
    			{
    				q.push(end2);
    			}
    			else
    			{
    				q.push(end);
    			}
    		}
    		if(map[end.zuo]=='D')
    		{
    			node end2=end;
    			end2.x=end.x+0;
    			end2.y=end.y-1;
    			end2.zuo=end.zuo;
    			if(ji(end2.x,end2.y,ex,ey)<ji(end.x,end.y,ex,ey))
    			{
    				q.push(end2);
    			}
    			else
    			{
    				q.push(end);
    			}
    		}
    		if(map[end.zuo]=='L')//zuo
    		{
    			node end2=end;
    			end2.x=end.x-1;
    			end2.y=end.y+0;
    			end2.zuo=end.zuo;
    			if(ji(end2.x,end2.y,ex,ey)<ji(end.x,end.y,ex,ey))
    			{
    				q.push(end2);
    			}
    			else
    			{
    				q.push(end);
    			}
    		}
    		if(map[end.zuo]=='R')
    		{
    			node end2=end;
    			end2.x=end.x+1;
    			end2.y=end.y+0;
    			end2.zuo=end.zuo;
    			if(ji(end2.x,end2.y,ex,ey)<ji(end.x,end.y,ex,ey))
    			{
    				q.push(end2);
    			}
    			else
    			{
    				q.push(end);
    			}
    		}
    	}
    	if(ff)
    	{
    		printf("%d\n",ans);
    	}
    	else
    	{
    		printf("-1\n");
    	}
    }
    
    int main()
    {
    	
    	scanf("%d",&T);
    	while(T--)
    	{
    		while(!q.empty())
    		{
    			q.pop();
    		}
    		scanf("%d%d%d",&ex,&ey,&t);
    		scanf("%s",map);
    		ff=false;
    		ans=INF;
    		node ks;
    		ks.x=0;
    		ks.y=0;
    		ks.step=0;
    		ks.zuo=-1;
    		q.push(ks);
    		wc();	
    	}
    	return 0; 
    }

[Edit]: http://acm.uestc.edu.cn/#/problem/editor/758