poj--2243 BFS

广搜题，参考了别人的代码，自己还不是很理解。。

编译器能通过，但是提交就不行，只得添加了一句

“

using namespace std;

”

才过，不知道什么原因。

//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

#define MAXN 8 + 10

struct Node
{
    int x;
    int y;
    int step;
};

int dx[8] = {-1, -1, 1, 1, -2, -2, 2, 2};
int dy[8] = {-2, 2, -2, 2, -1, 1, -1, 1};

bool visited[9][9];

char start[3], end[3];

int bfs();

int main()
{
#ifdef LOCAL
    freopen("C:\\Users\\Administrator\\Desktop\\Temp\\ACMTempIn.txt", "r", stdin);
    //freopen("C:\\Users\\Administrator\\Desktop\\Temp\\ACMTempOut.txt", "w", stdout);
#endif

    int result;
    while( scanf("%s%s", start, end) != EOF)
    {
        // 算法主体
        result = bfs();

        // 数据输出
        printf("To get from %s to %s takes %d knight moves.\n", start, end, result);
    }


    return 0;
}

int bfs()
{
    queue<Node> q;
    memset(visited, false, sizeof(visited));

    int x = start[0] - 'a' + 1;
    int y = start[1] - '0';
    int x1 = end[0] - 'a' + 1;
    int y1 = end[1] - '0';

    Node n;
    n.x = x;
    n.y = y;
    n.step = 0;
    q.push(n);
    visited[x][y] = true;
    while(!q.empty())
    {
        Node temp = q.front();
        q.pop();
        if(temp.x == x1 && temp.y == y1)
            return temp.step;
        for(int i = 0; i < 8; i++)
        {
            x = temp.x + dx[i];
            y = temp.y + dy[i];
            if(x < 1 || x > 8 || y < 1 || y > 8)
                continue;
            if(visited[x][y] == false)
            {
                Node temp1;
                temp1.x = x;
                temp1.y = y;
                temp1.step = temp.step + 1;
                q.push(temp1);
                visited[x][y] = true;
            }
        }
    }
}