跳至正文

USACO 2.4.2 Overfencing 解题报告

  • OI路程

题目看了之后容易发现就是广搜,从两个入口对全图进行广搜,搜到最后一个所需要的路程就是答案,广搜实现一点儿也不难,我的实现感觉还是比较好的,用一个宏和一个函数实现这个功能,然后用数字代表前进的方向,0:北,1:南,2:西,3:东。 但这题难的地方我觉得是把图转化成数据和寻找入口,其实难也不难,只是希望实现的代码简单些。刚开始我想根据变量循环的位置来判断,但这种方法的弊端就是代码量太大,要好多好多的判断,难的写,就直接使用-和|(墙的标识。)来标记数据就可以了,发现这个实现很简单,但是麻烦的就是找入口,最后我还是用了好多代码。 最开始我是把图转化成为数组的值之后再在数组里寻找,这么实现的话可以,只是说代码要多好几行,就换了种方法,放到和读取数据的循环了(看不懂这些话就看代码吧。) 代码: de lang="c">/ LANG: C ID: yylogoo1 PROG: maze1 / #include #include #define UP 1 #define DOWN 2 #define LEFT 4 #define RIGHT 8 //为0和39都提供空间, 在程序处理中会方便些 int map[102][40]; int ways[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int queue[3800][2]; int mark[101][39]; int head, end; int w, h; void enqueue(int i, int j, int k) { if(mark[i][j]){ return; } queue[end][0] = i; queue[end][1] = j; mark[i][j] = k; end++; } void exqueue(int *a) { assert(head h || b <1 b> w){ return 0; } return 1; } int main(void) { int i, j; char ch; int t[2]; freopen("maze1.in", "r", stdin); freopen("maze1.out", "w", stdout); scanf("%d%d\n", &w, &h); for(i = 1; i <2>

发表回复

您的电子邮箱地址不会被公开。