南山网站制作,青州网站,网站建设培训心得体会,有关网站建设的图片题干#xff1a;
Uva的题目就不粘贴题干了#xff0c;#xff0c;直接上题意吧。
有你一个独轮车#xff0c;车轮有5种颜色#xff0c;为了5中颜色的相对位置是确定的。有两种操作#xff1a;1.滚动#xff1a;轮子必须沿着顺时针方向滚动#xff0c;每滚动一次会到达…题干
Uva的题目就不粘贴题干了直接上题意吧。
有你一个独轮车车轮有5种颜色为了5中颜色的相对位置是确定的。有两种操作1.滚动轮子必须沿着顺时针方向滚动每滚动一次会到达另一个格子着地的颜色会改变顺时针转。例如当前是绿色着地下一次就是黑色依次是红蓝白。2.转动就是改变了轮子的方向不改变颜色转动每次只能选择左转90度或者右转90度即不能掉头。车子每向前走一格滚动耗时1秒拐弯转动耗时1秒。
开始时方向朝北轮子接触地面的颜色为绿色求出一条耗时最短的路线到达终点时使得车子接触地面的也为绿色方向无所谓。
解题报告 题意解释清楚了就是个简单的bfs了只是需要记录的东西比较多之前最多就是考虑个方向比如这题【HDU - 1254 】推箱子 双bfs现在再加个颜色的记录就是了。。vis[x][y][方向][颜色]。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;struct Node {int x,y;int dir,col,time;Node(){}Node(int x,int y,int dir,int col,int time):x(x),y(y),dir(dir),col(col),time(time){}
} st,ed;
int n,m;
char maze[55][55];
int nx[4] {0,-1,0,1};//左上右下
int ny[4] {-1,0,1,0};
bool vis[55][55][5][5];
bool ok (int x,int y) {if(x 1 x n y 1 y m) return 1;return 0 ;
}
int bfs() {memset(vis,0,sizeof vis);vis[st.x][st.y][1][0] 1;queueNode q;q.push(st);int tx,ty,tc,td;while(!q.empty()) {Node cur q.front();q.pop();if(cur.x ed.x cur.y ed.y cur.col 0) return cur.time;tc (cur.col 1) % 5;tx cur.x nx[cur.dir];ty cur.y ny[cur.dir];if(ok(tx,ty) maze[tx][ty] ! # vis[tx][ty][cur.dir][tc] 0) {vis[tx][ty][cur.dir][tc] 1;q.push(Node(tx,ty,cur.dir,tc,cur.time1));}td (cur.dir 1) % 4;if(vis[cur.x][cur.y][td][cur.col] 0) {vis[cur.x][cur.y][td][cur.col] 1;q.push(Node(cur.x,cur.y,td,cur.col,cur.time1));} td (cur.dir - 1 4) % 4;if(vis[cur.x][cur.y][td][cur.col] 0) {vis[cur.x][cur.y][td][cur.col] 1;q.push(Node(cur.x,cur.y,td,cur.col,cur.time1));}}return -1;
}
int main()
{int iCase 0;while(~scanf(%d %d,n,m)) {if(n 0 m 0) break;for(int i 1; in; i) {scanf(%s,maze[i]1);}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[i][j] S) st Node(i,j,1,0,0);if(maze[i][j] T) ed Node(i,j,0,0,0);}}if(iCase) puts();printf(Case #%d\n,iCase);int ans bfs();if(ans -1) puts(destination not reachable);else printf(minimum time %d sec\n,ans);}return 0 ;}
总结 代码的书写告诉我们这题只需要一个queue就可以了如果不这么写的话可能需要一个pq才可以、、比如你把转向和前进算在算在一步当中然后time2那就需要pq了、、
