2.1 最基础的“穷竭搜索” 深度优先搜索
一个房间上有红色的瓦和黑色的瓦片,给出红瓦和黑瓦的位置和人所占的位置,求人最多能走过多少片瓦?
(条件为:人行走过程中只能走黑瓦,且人的初始位置为黑瓦)
输入描述:输入的字符里面只有三种字符:
“@”—–表示人(只能有一个该字符)
“.”—–表示黑瓦
“#”—–表示红瓦
样例:
Sample Input
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#.
Sample Output
45
#ifndef ONLINE_JUDGE #pragma warning(disable : 4996) #endif #include <iostream> using namespace std; #define MAX_W 20 #define MAX_H 20 char room[MAX_W][MAX_H]; int W, H; const int direction[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, }; int step = 0; int dfs(const int& x, const int& y) { room[x][y] = '#'; ++step; for (int i = 0; i < 4; ++i) { int nx = x + direction[i][0]; int ny = y + direction[i][1]; if (nx >= 0 && nx < W && ny >= 0 && ny < H && room[nx][ny] == '.') { dfs(nx, ny); } } return step; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while (cin >> W >> H, W > 0) { step = 0; int x, y; for (y = 0; y < H; ++y) { for (x = 0; x < W; ++x) { cin >> room[x][y]; } } bool found = false; for (x = 0; x < W; ++x) { for (y = 0; y < H; ++y) { if (room[x][y] == '@') { found = true; break; } } if (found) { break; } } cout << dfs(x, y) << endl; } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 1979 Red and Black 《挑战程序设计竞赛(第2版)》练习题答案