嗯....

 

这道题是一个标准的bfs，只要背过了bfs 的模板，这道题小菜一碟...

 

首先先看题目：

 

题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入输出格式

输入格式：

 

一行四个数据，棋盘的大小和马的坐标

 

输出格式：

 

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

 

输入输出样例

输入样例#1：

3 3 1 1

输出样例#1：

0    3    2    3    -1   1    2    1    4    首先先讲一下思路： 首先 bfs 肯定要用队列，两个队列分别存点的横、纵坐标，然后用nx和my两个数组分别存储马下一步能到达的方向，vis数组判断是否访问， ｇ数组存棋盘，马每到一个点，首先将vis变为１,并且将横、纵坐标入队，然后进行bfs，将能一步到达的点储存，并且判断它是否越界， 然后是否将其入队，最后输出结果即可... 能想到用nx和ny两个数组来存储马前进的方向是此题的重点，能背过 bfs 的模板是此题前提与关键 下面是AC代码，外加解析：

1 #include
       
         2 //#include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6  7 using namespace std; 8  9 int g[401][401];//存棋盘 10 11 queue 
            
              q, q1;//q队列存横坐标,q1队列存纵坐标 12 13 int nx[8] = {1,2,2,1,-1,-2,-2,-1};//表示马横坐标的八种变化 14 int my[8] = {2,1,-1,-2,-2,-1,1,2};//表示马纵坐标的八种变化，为此题的重点15 bool vis[401][401]; //是否访问 16 17 int main(){18 int n, m;19 int x, y;20 memset(g,-1,sizeof(g));//初始化棋盘 21 scanf("%d%d",&n,&m);22 scanf("%d%d",&x,&y);23 g[x][y] = 0; 24 vis[x][y] = 1; 25 q.push(x);26 q1.push(y);27 // 开始进行 bfs，此题的框架28 while (!q.empty() ){29 int u = q.front();//将先前一个马的位置存储下来 30 int v = q1.front();31 q.pop();32 q1.pop();33 for(int i = 0; i <= 7; i++){34 int x1 = u + nx[i];//更新马的位置 35 int y1 = v + my[i];36 if (x1 > 0 && x1 <= n && y1 > 0 && y1 <= m && vis[x1][y1] == 0)//判断是否越界和是否被访问过 37 {38 vis[x1][y1] = 1;39 g[x1][y1] = g[u][v] + 1;// 到达此点的步数等于到达上一个点的步数加一 40 q.push(x1); //将新的位置入队 41 q1.push(y1);42 } 43 }44 }45 for(int i = 1; i <= n; i++){46 for(int j = 1; j <= m; j++){47 printf("%-5d",g[i][j]);48 //cout<
             
              <
              
               <
              
             
            
           
          
         
        
       

 

在这道题中，最终的输出方式与往常不同，请见下：

 

左对齐宽5格可以有两种输出方法：

　　

 

　　1.使用printf:

　　　　(1)对齐：

　　　　printf中的左对齐表示为在%后加-

　　　　printf中的右对齐表示为在%后加+

　　　　(2)宽ｘ格：(x为数)

　　　　printf中的宽x格表示为在对齐符号后加x

　　

　   2.使用cout:

　　　　(1)对齐：

　　　　cout中的左对齐为在要输出的数之前加 <<left<<

　　　　cout中的右对齐为在要输出的数之前加 <<right<<

　　　　(2)宽ｘ格：(x为数)

　　　　cout中的宽x格为只需在对齐操作和要输出的数之间加 <<setw(x)<<

 

 

注意：

cout中的操作简单，但比较慢，并且在使用cout做上述操作时，需要加头文件 <iomanip>