首页 > 代码库 > POJ-3050 Hopscotch(穷竭搜索,DFS,回溯法)
POJ-3050 Hopscotch(穷竭搜索,DFS,回溯法)
http://poj.org/problem?id=3050
Calm Down FIRST
题意:给定一个5*5的地图,每个格子上有一个数字。从一个格子出发(上下左右4个方向),走5步将数字连起来可以构造出一个6位数。问该地图可以构造出多少个不同的6位数。
分析:可以对每个格子做深度优先遍历,构造出所有数字,但要注意不要重复计数。在这里,我使用了set来保存已构造出的数字,结果就是set中的元素个数。
#include <cstdio> #include <set> #include <algorithm> using namespace std; //输入 int a[5][5]; set<int> st; //保存已构造的数字 const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; //深度优先遍历所有可能的构造 void dfs(int x, int y, int k, int num){ if(k == 6){ st.insert(num); return; } for(int i = 0; i < 4; i ++){ int nx = x + dx[i], ny = y + dy[i]; if(0 <= nx && nx < 5 && 0 <= ny && ny < 5){ k ++; dfs(nx, ny, k, num * 10 + a[nx][ny]); k --; } } } void solve(){ //对每个点作为起点,做深度优先遍历构造序列 for(int i = 0; i < 5; i ++){ for(int j = 0; j < 5; j ++){ dfs(i, j, 1, a[i][j]); } } printf("%d\n", st.size()); } int main(int argc, char const *argv[]){ for(int i = 0; i < 5; i ++){ for(int j = 0; j < 5; j ++) scanf("%d", &a[i][j]); } solve(); return 0; }
POJ-3050 Hopscotch(穷竭搜索,DFS,回溯法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。