Aug 19, 2011

An example of the breadth-first search

You can use the breadth-first search to process every state like the depth-first search.

When you want to search the shortest path for search space like a maze, the breadth-first search is a good solution for you because you have to search the same state so many times with the depth first-search.

The breadth-first search has a weak point. It needs memory that is proportional to a number of state.


This is an example of the breadth-first search:


- Description
You have a maze which size is M * N. The maze consists of path and wall.
You can move 4 direction (up, down, right and left) in one turn.
Solve the shortest path from the start to the goal.
- Constraint
N, M >= 100
- Sample Input
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
- Sample Output
22
My solution is like this. You can find it on my github repository.
#include 
#include 
#include 
using namespace std;

const int INF = 1000000;
const int MAX_N = 100;
const int MAX_M = 100;

typedef pair P;
char maze[MAX_N][MAX_M+1];  // maze
int n, m;   // size of maze
int sx, sy; // start position
int gx, gy; // goal position

//shortest path for each point
int d[MAX_N][MAX_M];

//vector for for moving direction
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

//solve the shortest path from (sx, sy) to (gx, gy)
int bfs() {
  queue

q; //initialize every point with INF before search for(int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { d[i][j] = INF; } } q.push(P(sx,sy)); d[sx][sy] = 0; while(q.size()) { P tmp = q.front(); q.pop(); //if you find goal then you finish search if ((tmp.first == gx)&&(tmp.second == gy)){ break; } for(int i = 0; i < 4; i++) { int nx = tmp.first + dx[i]; int ny = tmp.second + dy[i]; if ((0 <= nx) && (nx < n) && (0 <= ny) && (ny < m) && (maze[nx][ny] != '#') && (d[nx][ny] == INF)) { // if d[nx][ny] == INF then it is a position that // you have already visited. q.push(P(nx,ny)); d[nx][ny] = d[tmp.first][tmp.second] + 1; } } } return d[gx][gy]; } void solve() { int res = bfs(); cout << res << endl; } int main(int argc, char* argv[]) { if (argc != 2) { cout << "./a.out "; return 1; } ifstream ifs(argv[1]); if (!ifs) { cout << "can't open file:" << argv[1] << endl; return 1; } string buf; getline(ifs, buf); sscanf(buf.c_str(), "%d %d", &n, &m); for(int i = 0; i < n; i++) { getline(ifs, buf); for (int j = 0; j < m; j++) { maze[i][j] = buf[j]; if (maze[i][j] == 'S') { sx = i; sy = j; } if (maze[i][j] == 'G') { gx = i; gy = j; } } } solve(); return 0; }

Aug 18, 2011

Lake Counting(POJ No.2386)


This is a good example of Depth-First Search.

Description

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.
Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.
Output

* Line 1: The number of ponds in Farmer John's field.
Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
Sample Output

3

You can find my solution on github:

Aug 5, 2011

g++ compile error: declaration of "XXX" shadows a parameter

I found below error when I compiling C++ program with g++:
declaration of "XXX" shadows a parameter
Acording to the forum in cprogramming.com, which titile is "declaration of "blah" shadows a parameter??", you see this when you make derived class and don't initialize it with a constructor initialization list.