深搜!可剪枝!
以后,写深搜的时候,最好用flag标记下,而且,回溯的时候,应采用本题写法!
#include<stdio.h> #include<string.h> int dir[][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}; bool map[30][30],flag; char path[100]; int p,q; void dfs(int x,int y,int sum,int top) { if(flag) return ; int i,tempx,tempy; if(sum==p*q) { flag=true; return ; } for(i=0;i<8;i++) { tempx=x+dir[i][0];tempy=y+dir[i][1]; if(1<=tempx&&tempx<=q&&1<=tempy&&tempy<=p) { if(map[tempx][tempy]) { map[tempx][tempy]=false; path[top+1]=tempx-1+'A';path[top+2]=tempy+'0'; dfs(tempx,tempy,sum+1,top+2); if(flag==false) { map[tempx][tempy]=true; } else return ; } } } } int main() { int T,i,sum,top; scanf("%d",&T); for(i=1;i<=T;i++) { scanf("%d%d",&p,&q); sum=0;top=1;flag=false; printf("Scenario #%d:\n",i); memset(map,true,sizeof(map)); map[1][1]=false; sum=1; path[1]='A';path[2]='1';top=2; dfs(1,1,sum,top); if(flag) for(int k=1;k<=p*q*2;k++) printf("%c",path[k]); else printf("impossible"); printf("\n\n"); } return 0;
您还没有登录,请您登录后再发表评论
北大POJ2488-A Knight's Journey 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
c表示有多少种珍珠 ai 表示第i种珍珠所需的数量 pi 表示第i种珍珠的价钱 每买一种珍珠都需要付额外的10 * pi的钱,便宜的珍珠可以用贵的珍珠来代替,求最少的钱的总数。
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。可以按照分类,在POJ上做题。
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem....
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
poj-2528 Mayor's posters 测试数据及答案
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ3006-Dirichlet's Theorem on Arithmetic Progressions 解题报告+AC代码
POJ1584 -A Round Peg in a Ground Hole 测试数据。数据来源 Mid-Atlantic 2003 问题D
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
晒代码之二——多重背包(POJ1276)
相关推荐
北大POJ2488-A Knight's Journey 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
c表示有多少种珍珠 ai 表示第i种珍珠所需的数量 pi 表示第i种珍珠的价钱 每买一种珍珠都需要付额外的10 * pi的钱,便宜的珍珠可以用贵的珍珠来代替,求最少的钱的总数。
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。可以按照分类,在POJ上做题。
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem....
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
poj-2528 Mayor's posters 测试数据及答案
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ3006-Dirichlet's Theorem on Arithmetic Progressions 解题报告+AC代码
POJ1584 -A Round Peg in a Ground Hole 测试数据。数据来源 Mid-Atlantic 2003 问题D
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
晒代码之二——多重背包(POJ1276)