Chinaunix首页 | 论坛 | 博客
  • 博客访问: 433928
  • 博文数量: 103
  • 博客积分: 5010
  • 博客等级: 大校
  • 技术积分: 971
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-11 17:22
文章分类
文章存档

2008年(77)

2007年(26)

我的朋友

分类: C/C++

2008-04-06 18:49:34

#include <stdio.h>
#include <string.h>
typedef struct{
        int level;
        int row;
        int col;
}position;
position queue[90000];
int chess[300][300];
int x[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int y[8] = {2, 1, -1, -2, -2, -1, 1, 2};
static void input_init(position *begin, position *end, int *wide);
static void bfs(position *begin, position *end, int *wide);
int main(int argc, char **argv)
{
        int tests;
        int wide;
        position begin, end;
        scanf("%d", &tests);
        getchar();
        while(tests--){
                input_init(&begin, &end, &wide);
                bfs(&begin, &end, &wide);
        }
        return 0;
}

static void input_init(position *begin, position *end, int *wide)
{
        scanf("%d", wide);
        getchar();

        scanf("%d %d", &(begin->row), &(begin->col));
        getchar();
        scanf("%d %d", &(end->row), &(end->col));
        getchar();

        return;
}

static void bfs(position *begin, position *end, int *wide)
{
        int templevel = 0, head = 0, tail = 0, flag = 0, d;
        position temp, newtemp;

        memset(chess, 0, sizeof(chess));
        memset(queue, 0, sizeof(queue));

        if((begin->row == end->row) && (begin->col == end->col)){
                printf("%d\n", flag);
                return;
        }

        chess[begin->row][begin->col] = 1;
        begin->level = 0;
        queue[tail++] = *begin;

        while(head <= tail){
                temp = queue[head++];
                templevel = temp.level + 1;

                for(d = 0; d < 8; d++){
                        newtemp.row = temp.row + x[d];
                        newtemp.col = temp.col + y[d];
                        newtemp.level = templevel;
                        if((newtemp.row == end->row) && (newtemp.col == end->col)){
                                printf("%d\n", newtemp.level);
                                return;
                        }
                        if((newtemp.row >= 0) && (newtemp.row < *wide) && \
                                (newtemp.col >= 0) && (newtemp.col < *wide) \
                                 && (chess[newtemp.row][newtemp.col] == 0)){
                                queue[tail++] = newtemp;
                                chess[newtemp.row][newtemp.col] = 1;
                        }
                }
        }
        return;
}

阅读(813) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~