首页 > 代码库 > HDU1312 Red and Black 题解
HDU1312 Red and Black 题解
一条递归搜索法题目,使用递归搜索法,但是实际不用重复计算方格。
思路是:
1 每搜索一个方格就改变当前方格的值为 ‘*’,或者任何其他非‘.‘的值,代表该方格已经走过了
2 递归的时候不回复这个方格的值,就实际上不用重复搜索这个方格了,故此不用回溯
#include <stdio.h> #include <iostream> #include <string> #include <vector> using namespace std; int R, C, blacks; vector<string> board; inline bool isLegal(int r, int c) { return r>=0 && c>=0 && r<R && c<C && board[r][c] == '.'; } void getBlacks(int r, int c) { blacks++; board[r][c] = '*'; if (isLegal(r-1, c)) getBlacks(r-1, c); if (isLegal(r+1, c)) getBlacks(r+1, c); if (isLegal(r, c-1)) getBlacks(r, c-1); if (isLegal(r, c+1)) getBlacks(r, c+1); } int main() { string s; while (cin>>C>>R && C) { board.clear(); for (int i = 0; i < R; i++) { cin>>s; board.push_back(s); } blacks = 0; for (unsigned i = 0; i < board.size(); i++) { for (unsigned j = 0; j < board[0].size(); j++) { if ('@' == board[i][j]) { getBlacks((int)i, (int)j); goto out; } } } out:; printf("%d\n", blacks); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。