即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

POJ 1979 Red and Black

编程语言 B_Patrick 25℃ 0评论
本文目录
[隐藏]

1.Description


There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one
of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.





Write a program to count the number of black tiles which he can reach by repeating the moves described above.

1.1.Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in
the x- and y- directions, respectively. W and H are not more than 20.





There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.





‘.’ – a black tile


‘#’ – a red tile


‘@’ – a man on a black tile(appears exactly once in a data set)


The end of the input is indicated by a line consisting of two zeros.

1.2.Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

1.3.Sample Input

6 9


….#.


…..#


……


……


……


……


……


#@…#


.#..#.


11 9


.#………


.#.#######.


.#.#…..#.


.#.#.###.#.


.#.#..@#.#.


.#.#####.#.


.#…….#.


.#########.


………..


11 6


..#..#..#..


..#..#..#..


..#..#..###


..#..#..#@.


..#..#..#..


..#..#..#..


7 7


..#.#..


..#.#..


###.###


…@…


###.###


..#.#..


..#.#..


0 0



1.4.Sample Output

45

59

6

13

2.How to solve?

        The problem  asked us to figure out how many black squares are adjacent to the square where the man stand directly or indirectly.So we use BFS
here to obatin the number of continuous squares(DFS,as the recommended way ,would also be OK but I ‘ve not tried it yet).A deque in STL is used here. In the while loop. we add the adjacent square of the current square in each loop, so we can guarantee that
all of the asked squares could be traveled sequenctially.

        Here is the Accepted code:




#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef vectorvec;
typedef vectormat;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const double eps = 1e-7;
bool a[22][22];//the map
bool v[22][22];//visited
int dirX[4] = { 1,0,-1,0 };
int dirY[4] = { 0,1,0,-1 };
struct point{
 int x; int y;
 point() { x = y = 0; }
 point(int X, int Y) { x = X; y = Y; }
 point(const point &p) { x = p.x; y = p.y; }
};

dequeque;//for bfs
int main() {/*at first test one data*/
 
 //ifstream ifs;
 //ifs.open("D:\\documents\\programDatas\\POJ1979\\test.txt", ifstream::in);
 int m, n;//the size
 while (cin >> n >> m &&n) {
  memset(a, 0, sizeof(a)); memset(v, 0, sizeof(v));
  point ini;
  for (int i = 1; i <= m; i++) {
   for (int j = 1; j <= n; j++) {
    char temp;
    cin >> temp;
    if (temp ==  '#')a[i][j] = 1;
    else if (temp == '@') {
     ini.x = i;
     ini.y = j;
    }
   }
  }
  //debugging
  /*for (int i = 1; i <= m; i++) {
   for (int j = 1; j <= n; j++) {
    cout << a[i][j] << " ";
   }
   cout << "\n";
  }
  cout <= 1) && (curX <= m)
     && (curY >= 1) && (curY <= n)
     && v[curX][curY] == 0 && a[curX][curY] == 0) {
     que.push_back(point(curX, curY));
     v[curX][curY] = 1;
    }
   }
  }
  cout << ans << endl;
 }
 //system("pause");
 return 0;
}






转载请注明:CodingBlog » POJ 1979 Red and Black

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情