/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击： 链接被删请百度： CSDN tt2767 ///////////////////////////////////////////////////////////////////////////////////////////////////////
这题从中午做到晚上啊，收获还是比较多的。。。
学到的几点： 1.状态压缩：把状态压成二进制，通过查看二进制的每一位来判断状态。 2.带状态的bfs，虽然原来做过一道，但之前是还是不太明白 3.把地图数据化表示很有用 4.自己包装输入 5.。。。。。。。。。。
题解： 先把输入的数据处理一下，记录起点之后，数据化地图： 墙为-1，宝藏为1，2，，4，8(二进制就是0001，0010，0100，1000)，起点和路都为0.
每次通过加和记录已找到宝藏的状态 eg：找到了2，8记录为10（0010+1000=1010）
宝藏可能在任何地方，如果在墙里面，直接输出-1；
;LL;const int INF = 0x3f3f3f3f ;PI = acos(0.0) * 2.0;const int N = 200;const int dx[]={0,1,0,-1};const int dy[]={1,0,-1,0};const int change[] ={0,1,2,4,8};struct P{int x,y,step,num;P(int x,int y,int step,int num):x(x),y(y),step(step),num(num){}P(){}};P s;bool vis[N][N][N];char input[N][N];int maze[N][N];int sum,n,m;bool flag;//是否有宝物在墙里？int bfs();bool pass(P);//不管走没走过，这个位置是可以走的bool read();int main(){while( read() )printf(“%d\n”,bfs());return 0;}int bfs(){if(flag) return -1; //如果在墙里是不可能找全的memset(vis,0,sizeof(vis));queue<P> q;vis[s.x][s.y][s.num] = 1;q.push(s);while(!q.empty()){P p = q.front();q.pop();if(p.num == sum ) return p.step;for(int i = 0 ; i < 4 ; i++){P now = p; //先继承上一次的属性now.x += dx[i];now.y += dy[i];if( pass(now) ){if(maze[now.x][now.y] > 0 ) // 本题关键步骤！！{cnt = 0;//二进制移动位置while( mark1%2 == 0 ) //查找二进制中宝藏标记{mark1 >>= 1;//每次没有找到，二进制右移一位cnt++; //统计右移次数}if( (mark2 >> cnt)%2 == 0 ) //没捡过此宝藏，就把它捡起来{now.num += maze[now.x][now.y];}}if(!vis[now.x][now.y][now.num]){now.step = p.step + 1;vis[now.x][now.y][now.num] = 1;q.push(now);}}}}return -1;}bool read(){memset(input,’\0′,sizeof(input));memset(maze,0,sizeof(maze));if(scanf(“%d%d”,&n,&m) != 2 || !(n+m)) return false;for(int i = 1 ; i <= n ; i++){getchar();for(int j = 1 ; j <= m ; j++){scanf(“%c”,&input[i][j]);if(input[i][j] == ‘.’) //地图数据化{maze[i][j] = 0;}else if(input[i][j] == ‘@’){maze[i][j] = 0;s = P(i,j,0,0);}else{maze[i][j] = -1;}}}sum = 0;flag = false;int k;scanf(“%d”,&k);for(int i = 1 ; i <= k ; i++){int x,y;scanf(“%d%d”,&x,&y);if(maze[x][y] < 0) flag = true; //在墙里的话标记一下maze[x][y] += change[i];sum+= maze[x][y];}return true;}bool pass(P z){return (0 < z.x && z.x<= n && 0 < z.y && z.y <= m && maze[z.x][z.y] != -1 );}
这种精神使人能在旅行中和大自然更加接近，
