小记:阿西吧!我就因为一个dir方向搞错了,写的是从左往右是上下左右,用的时候是按上左下右。。。
思路:bfs,首先我们假设没有楼梯的情况,那么问题就简单很多了,bfs随手可以打出来。打完后再继续
我们现在要添加可变的楼梯上去。
楼梯有个初始状态,然后有个到达楼梯旁边时的楼梯的状态,而这个状态时和你到达楼梯旁边的步数有关的,奇数步就是和初始状态相反的状态,反正相同
现在考虑第一种情况:
我们出现在楼梯的旁边,那么此时楼梯是否能让我们过去(根据到此的步数做决断)。不能让就不过去,改下一个方向继续判断。直到处理完所有方向。可以到达的就入队。
并且我们要对每个点保存下到这点最少的步数,用以减少不必要的操作。然后比较步数得到最少的。
最开始,我也以为这就是答案了,而且不超过一刻钟,我提交了代码,标准的WA。我默认。开始思考ing
我看到题目描述只有'.', 'S','T'可以停,停! 这一个字点醒了我,我在楼梯旁我是可以停的。!!
这点很关键。还好我想到了。于是我改。
我在方向后面加了一个停,[0,0]表示。在入队的时候还要加判断,不然会无限循环的。
我采用身边有'-',或者'|'来做标记要不要等一分钟。然后还加了一个记录,我在这楼梯旁的这个位置,我只停一次!
对只停一次。
我把自己的测试数据试了。
8 2
.T
..
.-
..
.-
..
.-
.S
答案是7没错,果断提交,自信心满满的。
回头一看,WA。。。 我TMD的黯然神伤了。这尼玛还有哪点没考虑到的。
实在是想不通了,点了点discuss,里面有测试数据,我拿来测了下,
3 4 S|.| -T-. .|..
我的程序跑出来的是6,尼玛真的是6啊,明明是7啊。6是怎么来的。。。。
我顿时觉得我可以在这里找到我的bug。我也顺便测了另一组数据
20 20 S.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.| |.|.|.|.|.|.|.|.|.|. .|.|.|.|.|.|.|.|.|.T
我的程序是37,答案是20,那些AC的测试的。
我顿时觉得,我的程序怎么是千仓百孔的。。。飙泪中。。。
开始从6是怎么出来的着手。
我一直自以为,以为方向数组是对的, 然后各种printf,终于让我知道了,我的dir搞错了。修改一下,
我上左下右的,int dir[5][2] = {{0,-1},{-1,0},{0,1},{1,0},{0,0}};
这样我循环的时候就是从0-5的,而0,2表示竖,1,3表示横,因此我只要对循环的i对2取模就可以知道是横还是竖了,0表示竖,1表示横
这样的目的是,在碰到楼梯时,假设它开始是竖,用0表示,step步后,到达了该楼梯旁边,那么此时该楼梯的状态就是 step&1, 然后看状态的结果和i%2是否相等
相等就是代表这楼梯我可以做。
如果是横,那么step后,状态为(1&step)^1. 再与i%2比较。相等亦是同上。
然后提交,AC啦!!!!!!!!!!!!!!!
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define REP(a,b,c) for(int a = b; a < c; ++a) #define eps 10e-8 const int MAX_ = 60; const int N = 100010; const int INF = 0x7fffffff; struct Point { int x, y; int step; }p2, p1; int dir[5][2] = {{0,-1},{-1,0},{0,1},{1,0},{0,0}}; int vis[MAX_][MAX_]; int a[MAX_][MAX_], num[MAX_][MAX_]; int n, m, k, ti; char str[MAX_][MAX_]; int bfs(Point x) { queue<Point> q; mst(vis, 0); mst(num, 0); x.step = 0; q.push(x); int ans = INF; bool flag = false; while(!q.empty()){ Point cur; cur = q.front(); q.pop(); if(cur.x == p2.x && cur.y == p2.y ){ ans = min(ans, cur.step); continue; //return cur.step; } //printf("%d %d %d\n", cur.x, cur.y, cur.step); REP(i, 0, 5){ Point nt; nt.x = cur.x + dir[i][1]; nt.y = cur.y + dir[i][0]; nt.step = cur.step+1; if(i == 4 && !flag)continue; if((nt.x > -1 && nt.x < n) && (nt.y > -1 && nt.y < m) && str[nt.x][nt.y] != '*'){//printf("[%d, %d %d]:%d %d\n", nt.x, nt.y, nt.step,dir[i][1],dir[i][0]); if(str[nt.x][nt.y] == '|'){ flag = true; int st = (1 & cur.step); if(st == i%2){ //printf("|:%d %d %d %d [%d %d %d]\n",i, cur.x, cur.y, cur.step, nt.x,nt.y,nt.step); nt.x = nt.x + dir[i][1]; nt.y = nt.y + dir[i][0]; } else continue; }else if(str[nt.x][nt.y] == '-'){ flag = true; //printf("ok\n"); int st = (1 & cur.step)^1; if(st == i%2){ //printf("-:%d %d %d %d [%d %d %d]\n",i, cur.x, cur.y, cur.step, nt.x,nt.y,nt.step); nt.x = nt.x + dir[i][1]; nt.y = nt.y + dir[i][0]; } else continue; } if((nt.x > -1 && nt.x < n) && (nt.y > -1 && nt.y < m) && str[nt.x][nt.y] != '*'){ if(!vis[nt.x][nt.y] || (nt.step < vis[nt.x][nt.y])){ vis[nt.x][nt.y] = nt.step; q.push(nt); } if(i == 4 && flag && !num[nt.x][nt.y]){ num[nt.x][nt.y] = 1; q.push(nt); } } } } } return ans; } int main(){ int T, cnt; //scanf("%d", &T); while(~ scanf("%d%d", &n, &m)){ cnt = 0; REP(i, 0, n){ scanf("%s", str[i]); REP(j, 0, m){ if(str[i][j] == 'S'){ p1.x = i; p1.y = j; }else if(str[i][j] == 'T'){ p2.x = i; p2.y = j; } } } int ans; ans = bfs(p1); printf("%d\n",ans); } return 0; } /* 8 2 .T .. .- .. .- .. .- .S */