BNU 25588 Elevator Trouble

  D. Elevator Trouble Time Limit: 2000msCase Time Limit: 1000msMemory Limit: 65536KB 64-bit integer IO format: %lld      Java class name: Main Submit   Status   PID: 25588 Font Size:  +   -   You are on your way to your first job interview as a program tester, and you are already late. The interview is in a skyscraper and you are currently in floor s, where you see an elevator. Upon entering the elvator, you learn that it has only two buttons, marked "UP u" and "DOWN d". You conclude that the UP-button takes the elevator u floors up (if there aren't enough floors, pressing the UP-botton does nothing, or at least so you assume), whereas the DOWN-button takes you d stories down (or none if there aren't enough). Knowing that the interview is at floor g, and that there are only f floors in the building, you quickly decide to write a program that gives you the amount of button pushes you need to perform. If you simply cannot reach the correct floor, your program halts with the message "use the stairs". Given input f, s, g, u and d (floors, start, goal, up, down), find the shortest sequence of button presses you must press in order to get from s to g, given a building of f floors, or output "use the stairs" if you cannot get from s to g by the given elevator.   Input The input will consist of one line, namely f s g u d, where 1 <= s, g <= f <= 1000000 and 0 <= u, d <= 1000000. The floors are one-indexed, i.e. if there are 10 stories, s and g be in [1, 10]. Output You must reply with the minimum numbers of pushes you must make in order to get from s to g, or output use the stairsif it is impossible given the configuration of the elvator. Sample Input Sample Input 1 10 1 10 2 1   Sample Input 2 100 2 1 1 0 Sample Output Sample Output 1 6   Sample Output 2 use the stairs Submit   Status   PID: 25588     code：

/**
題意：給你 f,s,g,u,d 這幾個數字
      總共可以走的點為從 1 到 f 
      要你從點 s 到達點 g
	  有兩種走法：往前走 u , 或者往後走 d
	  如果能到達則輸出最少的步數.否則輸出 use the stairs
算法：BFS
總結：就和本人第一個BFS 【POJ 3278 Catch That Cow 】簡直是一個模塊，
      很裸的 BFS了,稍微變換了條件腦袋就沒有反應過來 。 
      比賽的時候居然沒有做出來，還一直認為是 DP 才能解決
	  還好隊友 Orc 水過了。。。這種狀態是什麼節奏Orz 
*/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

const int maxn = 1000000 + 10;

int f,s,g,u,d;
int flag, step;

int vis[maxn];

struct Node{
	int p; //位置 
	int step; //步數 
};
queue<Node> q;
void bfs(int s)
{
	Node now, next;
	now = (Node) {s, 0};
	
	while(!q.empty()) q.pop();
	q.push(now);
	
	memset(vis, 0, sizeof(vis));
	vis[s] = 1;
	
	while(!q.empty())
	{
		now = q.front(); q.pop(); //取出並且彈出隊首 
		
		for(int i = 1; i <= 2; i++)
		{
			if(i == 1) next.p = now.p+u; //兩種走法 
			if(i == 2) next.p = now.p-d;
			
			if(next.p < 1 || next.p > f) continue; //越界 
			
			if(!vis[next.p])
		    {
    			vis[next.p] = 1;
    			next.step = now.step+1;
    			q.push(next);
    			
    			if(next.p == g) //到達終點 
    			{
			    	flag = 1;
			    	step = next.step;
			    	return;
			    }
    		}
		}	
	}
	return;
	
}
int main()
{
	while(scanf("%d%d%d%d%d", &f,&s,&g,&u,&d) != EOF)
	{
		if(s == g) //如果起點就是終點 
		{
			printf("0\n"); continue;
		}
		flag = 0; //標記 
		bfs(s); //搜索起點 
		if(flag) printf("%d\n", step); //能到達 
		else printf("use the stairs\n");
	}
	return 0;
}