本文主要是介绍POJ - 1979(深搜),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:点击打开链接
解析:
深搜无疑,搜的时候记得把当前点置为不可行,之后在搜周边点。另一个坑点是,要特别考虑@周边都是墙这种情况,此时输出0(只有他当前的那一个点)。
完整代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
const int maxn = 31;
char g[maxn][maxn];
int d[4][2] = {0 , 1 , 1 , 0 , 0 , -1 , -1 ,0};
void dfs(int si , int sj , int n , int m , int& cnt)
{for(int i = 0 ; i < 4 ; i ++){int x = si + d[i][0];int y = sj + d[i][1];if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '#') continue;g[x][y] = '#';cnt += 1;dfs(x , y , n , m , cnt);}
}int main()
{#ifdef DoubleQfreopen("in.txt" , "r" , stdin);#endif // DoubleQint n , m;while(cin >> n >> m){if(n == 0 && m == 0) break;string str;int si , sj;for(int i = 0 ; i < m ; i ++){cin >> str;for(int j = 0 ; j < n ; j ++){g[i][j] = str[j];if(str[j] == '@'){si = i;sj = j;}}}int cnt = 0;/*for(int i = 0 ; i < n ;i ++){for(int j = 0 ; j < m ; j ++){cout << g[i][j] << " ";}cout << endl;}*/dfs(si , sj , m , n , cnt);if(cnt == 0) cout << "1" << endl;else cout << cnt << endl;}
}
这篇关于POJ - 1979(深搜)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!