15道计算机算法设计与分析上机实验

#include <iostream> #include <queue> #define MAX_N 12 // 棋盘总数（包括添加的边界） #define NBRS 8 // 可达相邻方位数 using namespace std; int grid[MAX_N][MAX_N];// 棋盘 class Position{// 方位类 public : int row; int col; }; Position offset[NBRS]; // 初始化，移动的相对位移 void initOffset(){ offset[0].row = 2;offset[0].col = -1;// 右，上 offset[1].row = 2;offset[1].col = 1;// 右，下 offset[2].row = 1;offset[2].col = 2;// 下，右 offset[3].row = -1;offset[3].col = 2;// 下，左 offset[4].row = -2;offset[4].col = 1;// 左，下 offset[5].row = -2;offset[5].col = -1;// 左，上 offset[6].row = -1;offset[6].col = -2;// 上，左 offset[7].row = 1;offset[7].col = -2;// 上，右 } // 初始化，外围边界障碍 void initSet(){ memset(grid, 0, (MAX_N * MAX_N) * sizeof(int)); for (int i = 0; i < MAX_N; i++) {// 顶部和底部 grid[0][i] = grid[MAX_N - 1][i] = grid[1][i] = grid[MAX_N - 2][i] = -1; } for (int i = 0; i < MAX_N; i++) {// 左翼和右翼 grid[i][0] = grid[i][MAX_N - 1] = grid[i][1] = grid[i][MAX_N - 2] = -1; } } // 返回最短步数，-999则为无法到达 int FindPath(Position start, Position finish){ if (start.row == finish.row && start.col == finish.col) { return 0; } initOffset();// 初始化相对位移 queue<Position> Q;// 队列 Position here, nbr; here.row = start.row; here.col = start.col; grid[start.row][start.col] = 2; // 标记可达相邻方格 do{ for (int i = 0; i < NBRS; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) {// 未标记 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if (nbr.row == finish.row && nbr.col == finish.col) { return grid[finish.row][finish.col] - 2;// 已找到骑士终点位置 //break; } Q.push(nbr); } } if (Q.empty()) { return -999;// 无法到达 //break; } // 队列不空 here = Q.front();// 取队首，作为下一扩展结点 Q.pop();// 删除队首 }while (true); } // 将输入的a,b,c,d,e,f,g,h转换成相应数字 int getColNum(char c){ int row; switch (c) { case 'a': row = 1; break; case 'b': row = 2; break; case 'c': row = 3; break; case 'd': row = 4; break; case 'e': row = 5; break; case 'f': row = 6; break; case 'g': row = 7; break; case 'h': row = 8; break; default: row = -1; break; } return row; } int main(){ int count = 0;// 计数，当前第几组数据 while (true) { count ++; int hinder;// 障碍个数 cin >> hinder; if (hinder == -1) {// -1终止 break; } initSet();// 初始化数组 Position n;// 骑士起点 Position N;// 骑士终点 string loc;// 获取输入字符串 for (int i = 0 ; i < hinder; i++) { cin >> loc; grid[(loc[1] - '0') - 1 + 2][getColNum(loc[0]) - 1 + 2] = -1; } cin >> loc;// 骑士起点 n.row = (loc[1] - '0') - 1 + 2; n.col = getColNum(loc[0]) - 1 + 2; cin >> loc;// 骑士终点 N.row = (loc[1] - '0') - 1 + 2; N.col = getColNum(loc[0]) - 1 + 2; // // 打印棋盘 // for (int i = 0; i < MAX_N; i++) { // for (int j = 0; j < MAX_N; j++) { // cout << grid[i][j] << ","; // } // cout << endl; // } int pathLen = FindPath(n, N); if (pathLen == -999) { cout << "Board "<< count <<":not reachable" << endl; }else{ cout << "Board "<< count <<":" << pathLen <<" moves" << endl; } } cout << endl; return 0; }