csuoj 1119: Collecting Coins

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1119

1119: Collecting Coins

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 144 Solved: 35
[Submit][Status][Web Board]

Description

In a maze of r rows and c columns, your task is to collect as many coins as possible.

Each square is either your start point "S"(which will become empty after you leave), an empty square ".", a coin square "C" (which will become empty after you step on this square and thus collecting the coin), a rock square "O" or an obstacle square "X".

At each step, you can move one square to the up, down, left or right. You cannot leave the maze or enter an obstacle square, but you can push each rock at most once (i.e. You can treat a rock as an obstacle square after you push it).

To push a rock, you must stand next to it. You can only push the rock along the direction you're facing, into an neighboring empty square (you can't push it outside the maze, and you can't push it to a squarecontiaining a coin).For example, if the rock is to your immediate right, you can only push it to its right neighboring square.

Find the maximal number of coins you can collect.

Input

The first line of input contains a single integer T (T<=25), the number of test cases.

Each test case begins with two integers r and c (2<=r,c<=10), then followed by r lines, each with c columns.

There will be at most 5 rocks and at most 10 coins in each maze.

Output

For each test case, print the maximal number of coins you can collect.

Sample Input

3
3 4
S.OC
..O.
.XCX
4 6
S.X.CC
..XOCC
...O.C
....XC
4 4
.SXC
OO.C
..XX
.CCC

Sample Output

1
6
3

HINT

Source

湖南省第八届大学生计算机程序设计竞赛

分析；

BFS

AC代码；

  1 #include<vector>
  2 #include<list>
  3 #include<map>
  4 #include<set>
  5 #include<deque>
  6 #include<stack>
  7 #include<bitset>
  8 #include<algorithm>
  9 #include<functional>
 10 #include<numeric>
 11 #include<utility>
 12 #include<sstream>
 13 #include<iostream>
 14 #include<iomanip>
 15 #include<cstdio>
 16 #include<cmath>
 17 #include<cstdlib>
 18 #include<cstring>
 19 #include<ctime>
 20 #define LL long long
 21 
 22 using namespace std;
 23 int mp[20][20];
 24 int vis[20][20];
 25 int xadd[] = {1,-1,0,0};
 26 int yadd[] = {0,0,1,-1};
 27 struct node
 28 {
 29    int x;int y;
 30    int is;
 31    node(int _x, int _y, int _is)
 32    {
 33         x = _x; 
 34         y = _y;
 35         is = 0; 
 36    }
 37 };
 38 vector<node> C;
 39 int mx = 0;
 40 int ansnum = 0 ; 
 41 int n , m ;
 42 void debug()
 43 {
 44   for(int i = 1;i <= n;i ++)
 45   {
 46       for(int j = 1;j <= m;j ++)
 47           printf("%d ",mp[i][j]);
 48       printf("
");
 49   }
 50 }
 51 void bfs(int x, int y ,int ans)
 52 {
 53   //printf("%d %d
",x,y);
 54    if(mx == ansnum)
 55        return;
 56    vector<node> Q;
 57    Q.push_back(node(x,y,0));
 58    vis[x][y] = 1; 
 59    int l = 0; 
 60    int r = 0;
 61    while(l <= r )
 62    {
 63      for(int i = 0 ;i <= 3;i ++)
 64      {
 65        int tx = Q[l].x + xadd[i] ;
 66        int ty = Q[l].y + yadd[i] ;
 67        if(mp[tx][ty] >= 1 && !vis[tx][ty])
 68        {
 69          vis[tx][ty] = 1;
 70          r ++ ;
 71          if(mp[tx][ty] == 2)
 72          {
 73             Q.push_back(node(tx,ty,1));
 74             ans ++ ; 
 75          }
 76          else Q.push_back(node(tx,ty,0));
 77        }
 78      }
 79      l ++ ; 
 80    }
 81    if(ans > mx)
 82        mx = ans; 
 83    for(int i = 0;i < C.size();i ++)
 84      {
 85          if(!C[i].is)
 86          {
 87             for(int s = 0 ;s <= 3;s ++)
 88             {
 89                int tx = C[i].x + xadd[s];
 90                int ty = C[i].y + yadd[s];
 91                int ttx = C[i].x - xadd[s];
 92                int tty = C[i].y - yadd[s];
 93                //printf("%d %d %d %d
",tx,ty,ttx,tty);
 94                if(mp[tx][ty] == 1 && vis[ttx][tty] == 1)
 95                {
 96                    mp[tx][ty] = -1;
 97                    mp[C[i].x][C[i].y] = 1;
 98                    C[i].is = 1; 
 99                    bfs(C[i].x,C[i].y,ans);
100                    mp[tx][ty] = 1;
101                    mp[C[i].x][C[i].y] = 0;
102                    C[i].is = 0 ; 
103                }
104             }
105          }
106      }
107   for(int i = r; i >= 0 ;i --)
108   {
109       vis[Q[i].x][Q[i].y] = 0  ;
110       if(Q[i].is)
111       {
112          mp[Q[i].x][Q[i].y] = 2  ;
113       }
114   }
115 }
116 int main(){
117     int t ; 
118     scanf("%d",&t);
119     while(t--)
120     {
121          memset(mp,-1,sizeof(mp));
122          memset(vis,0,sizeof(vis));
123          scanf("%d %d",&n,&m);
124          char str[20];
125          int bex, bey ;
126          ansnum =0 ; 
127          C.clear();
128          for(int i = 1 ;i <= n;i ++)
129          {
130              scanf("%s",&str[1]);
131              for(int j = 1;j <= m; j ++)
132              {
133                if(str[j] == 'S')
134                {
135                  mp[i][j] = 1 ; 
136                  bex = i ; 
137                  bey = j ; 
138                }else if(str[j] == 'C')
139                {
140                  ansnum ++;
141                  mp[i][j] = 2; 
142                }else if(str[j] == 'X')
143                {
144                  mp[i][j] = -1; 
145                }else if (str[j] == 'O'){
146                  mp[i][j] = 0 ;
147                  C.push_back(node(i,j,0));
148                }else {
149                  mp[i][j] = 1; 
150                }
151              }
152          }
153          mx = 0 ; 
154          bfs(bex,bey,0);
155          printf("%d
",mx);
156     }
157     
158     return 0;
159 }

View Code