题目链接:http://poj.org/problem?id=2935
解题报告:刷到bfs明显的感觉有些难,这道题应该卡的有3~4天了吧!
首先说明一下bfs如何记录路径:在结构体中,用一个值来记录上一个的位置,然后再“回溯”(并不是真的回溯)到第一个元素,然后递归输出即可;
第二点:交换两个数的位运算方法:a^=b^=a^=b,看上去显得代码更有技术含量
第三点:注意输入值的顺序,我就在这卡了n久
#include<cstdio> #include<cstring> #include<queue> #define swap(a,b) a^=b^=a^=b using namespace std; const int maxn = 15; const int dir[4][2]={0,2,2,0,0,-2,-2,0}; const char ch[4]={'E','S','W','N'}; struct node { int x,y; int pre; char c; }q[maxn*maxn]; int sx,sy,ex,ey,num; int mp[maxn][maxn]; bool iswall( int x,int y,int i) { if ( i==0 && mp[x][y-1] ) return true; else if(i==1&&mp[x-1][y]) return true; else if(i==2&&mp[x][y+1]) return true; else if(i==3&&mp[x+1][y]) return true; else return false; } void print(int x) { if(x) { print(q[x].pre ); printf("%c",q[x].c); } } void bfs( ) { int front = 0, rear = 0; node frm = {sx,sy,0,0}; q[rear++] = frm; while(front < rear) { frm = q[front]; for( int i=0;i<4;i++) { node to = {frm.x+dir[i][0],frm.y+dir[i][1],front,ch[i]}; if(to.x < 2||to.x >12||to.y <2||to.y > 12) continue; if(!mp[to.x][to.y]&&!iswall(to.x,to.y,i)) { mp[to.x][to.y] = 1; q[rear] = to; if(to.x==ex&&to.y==ey) { print( rear );//printf("\nrear = %d front = %d",rear,front); return ; } ++rear; } } ++front; } } int main() { int a1,a2,b1,b2; while(scanf("%d%d",&sy,&sx)&&(sx||sy)) { scanf("%d%d",&ey,&ex); memset(mp,0,sizeof(mp)); ex = 2*ex;ey = 2*ey; sx = 2*sx;sy = 2*sy; mp[sx][sy] = 1; for(int i=0;i<3;i++) { scanf("%d%d%d%d",&b1,&a1,&b2,&a2); if( a1 == a2 ) { if(b1>b2) swap(b1,b2); for(int j=b1;j<b2;j++) mp[a1*2+1][j*2+2]=1; } else { if(a1>a2) swap(a1,a2); for(int j=a1;j<a2;j++) mp[2*j+2][b1*2+1]=1; } } if( sx==ex && sy ==ey ) { puts(""); continue; } bfs(); printf("\n"); } return 0; }
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
SPOJ3 AC程序 BF SPOJ3 AC程序 BF SPOJ3 AC程序 BF
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
西北工业大学POJ试题C++答案代码+课程设计
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
POJ 3131 双向BFS解立体八数码问题
北大POJ2002-Squares 解题报告+AC代码
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
POJ1837-Balance 解题报告+AC代码