首页 > 代码库 > CSU 1119 Collecting Coins

CSU 1119 Collecting Coins

bfs+dfs

很复杂的搜索题。

因为数据很小,rock最多只有5个,coin最多只有10个,移动rock最多4^5=1024种状态;

思路:

  每次先把当前状态能拿到的coin拿走,并将地图当前位置设为‘.‘ (拿走coin的位置为空)

  拿走coin后,在搜索一次,碰到rock判断是否能push动,能的话建立一个新地图,rock所在点设为‘.‘ (空),rock移动到的点设为‘X‘ (只能移动一次)。就这样递归下去,因为只有5个rock,最对递归5层。

  每次扫描完当前状态地图和以前拿到的最大值比较一下,取较大值 (有时候不移动rock拿到的coin更多!)

 

ps:开始为了少设置一个变量偷懒,结果得不偿失,卡了好久。。。看来以后要小心点,不要随便改动前面的值,宁可多敲点也别犯这种低级错误。。。

  1 #include <iostream>  2 #include <cstring>  3 #include <cstdio>  4 #include <algorithm>  5 #include <cmath>  6 #include <queue>  7 using namespace std;  8   9 char map[1050][20][20];  //第一维其实只要5就够了,当时一看状态1024就没多想,反正1024也没关系,数据小~~ 10 int visit[1050][20][20]; 11 int n,m,ma; 12  13 int dir[4][2]={0,1,0,-1,1,0,-1,0}; 14  15 struct node { 16     int x,y; 17 }st; 18  19 void cpy (int d,int s){ 20     for (int i=0;i<n;i++) 21         for (int j=0;j<m;j++) 22             map[d][i][j]=map[s][i][j]; 23 } 24  25 void rvisit (int o){ 26     for (int i=0;i<n;i++) 27         for (int j=0;j<m;j++) 28             visit[o][i][j]=0; 29 } 30  31 int bfs (int o,int ans,node st){//cout<<st.x<<" "<<st.y<<endl; 32     node a,b,c; 33     queue<node> q; 34     while (!q.empty()) 35         q.pop (); 36     q.push (st); 37     rvisit (o); 38     visit[o][st.x][st.y]=1; 39     while (!q.empty ()){ 40         a=q.front (); 41         q.pop (); 42         int xx,yy; 43         for (int i=0;i<4;i++){ 44             xx=a.x+dir[i][0]; 45             yy=a.y+dir[i][1]; 46             if (visit[o][xx][yy]) 47                 continue ; 48             if (xx<0||xx>=n||yy<0||yy>=m) 49                 continue ; 50             if (map[o][xx][yy]==X||map[o][xx][yy]==O) 51                 continue ; 52             if (map[o][xx][yy]==C){ 53                 ans++; 54                 map[o][xx][yy]=.; 55             } 56             b.x=xx;b.y=yy; 57             q.push (b); 58             visit[o][xx][yy]=1; 59         } 60     } 61     ma=max (ma,ans); 62     q.push (st); 63     rvisit (o); 64     visit[o][st.x][st.y]=1; 65     while (!q.empty ()){ 66         a=q.front ();//if (o==0)cout<<o<<":"<<a.x<<" "<<a.y<<endl; 67         q.pop (); 68         int xx,yy; 69         for (int i=0;i<4;i++){ 70             xx=a.x+dir[i][0]; 71             yy=a.y+dir[i][1]; 72             if (visit[o][xx][yy]) 73                 continue ; 74             if (xx<0||xx>=n||yy<0||yy>=m) 75                 continue ; 76             if (map[o][xx][yy]==X) 77                 continue ; 78             if (map[o][xx][yy]==O){ 79                 int xxx,yyy; 80                 xxx=xx+dir[i][0]; 81                 yyy=yy+dir[i][1]; 82                 if (xxx<0||xxx>=n||yyy<0||yyy>=m) 83                     continue ; 84                 if (map[o][xxx][yyy]==.){ 85                     cpy (o+1,o); 86                     map[o+1][xx][yy]=.; 87                     map[o+1][xxx][yyy]=X;//cout<<o<<":"<<a.x<<" "<<a.y<<"|"<<xx<<" "<<yy<<"|"<<xxx<<" "<<yyy<<endl; 88                     c.x=xx;c.y=yy; 89                     bfs (o+1,ans,c); 90                 } 91                  92                 continue ; 93             } 94             b.x=xx;b.y=yy;//if (o==0) cout<<a.x<<" "<<a.y<<"|"<<xx<<" "<<yy<<endl; 95             q.push (b); 96             visit[o][xx][yy]=1; 97         } 98     } 99 }100 101 int main (){102     int t;103     scanf ("%d",&t);104     while (t--){105         scanf ("%d%d",&n,&m);106         for (int i=0;i<n;i++){107             scanf ("%s",map[0][i]);108             for (int j=0;j<m;j++){109                 if (map[0][i][j]==S){110                     st.x=i;st.y=j;111                     //map[0][i][j]=‘.‘;112                 }113             }114         }//cout<<st.x<<" "<<st.y<<endl;cout<<map[0][st.x][st.y]<<endl;115         ma=0;116         bfs (0,0,st);117         printf ("%d\n",ma);118     }119     return 0;120 }

 

CSU 1119 Collecting Coins