华师一附中OI组

标题: P1443 马的遍历 [打印本页]
作者: admin    时间: 2018-5-11 10:56
标题: P1443 马的遍历
https://www.luogu.org/problemnew/show/P1443

题目描述
有一个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   

作者: lyc    时间: 2018-5-12 16:12
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<iomanip>
  6. const int maxn=440;
  7. using namespace std;
  8. int n,m;
  9. int qx[100010],qy[100010];
  10. int fx[8]= {2,-2,2,-2,-1,1,-1,1};
  11. int fy[8]= {1,1,-1,-1,2,2,-2,-2};
  12. int map1[maxn][maxn];
  13. int vis[maxn][maxn];
  14. int main()
  15. {
  16.     int x;
  17.     int y;
  18.     cin>>n>>m>>x>>y;
  19.     for(int i=1; i<=n; i++)
  20.         for(int j=1; j<=m; j++)
  21.             map1[i][j] = -1;
  22.     map1[x][y] = 0;
  23.     int st=1, ed=2;
  24.     qx[1] = x;
  25.     qy[1] = y;
  26.     vis[x][y] =1;
  27.     while(st != ed)
  28.     {
  29.         int nowx=qx[st];
  30.         int nowy=qy[st];
  31.         for(int i=0; i<=7; i++)
  32.         {
  33.             int xx=nowx+fx[i];
  34.             int yy=nowy+fy[i];
  35.             if (xx < 1 || xx > n || yy < 1 || yy > m || (map1[xx][yy] <= map1[nowx][nowy] + 1 && map1[xx][yy] + 1))
  36.                 continue;
  37.             map1[xx][yy]=map1[nowx][nowy]+1;
  38.             qx[ed] = xx;
  39.             qy[ed] = yy;
  40.             ed++;
  41.         }
  42.         st++;
  43.     }
  44.     for(int i=1; i<=n; i++)
  45.     {
  46.         for(int j=1; j<=m; j++)
  47.             cout<<left<<setw(5)<<map1[i][j];
  48.         cout<<endl;
  49.     }
  50.     return 0;
  51. }
复制代码
作者: liubo    时间: 2018-5-26 22:06
  1. #include<iostream>
  2. #include<cstring>
  3. #include<queue>
  4. #include<cstdio>
  5. using namespace std;
  6. const int maxn = 405;
  7. int field[maxn][maxn];
  8. int n,m,sx,sy;
  9. int dx[] = {-1,1,2,2,1,-1,-2,-2};
  10. int dy[] = {-2,-2,-1,1,2,2,1,-1};
  11. struct node{
  12.     int x;
  13.     int y;
  14.     node(int x = 0,int y = 0):x(x),y(y){}
  15. };
  16. queue<node> q;
  17. bool in(node k){
  18.     return k.x > 0 && k.x <= n && k.y > 0 && k.y <= m;
  19. }
  20. void bfs(){
  21.     while(!q.empty()){
  22.         node k = q.front(); q.pop();
  23.         for(int i = 0;i <= 7;i++){
  24.             node v = node(k.x + dx[i],k.y + dy[i]);
  25.             int &m = field[v.x][v.y];
  26.             if(in(v) && m == -1){
  27.                 int n = field[k.x][k.y];
  28.                 m = n + 1;
  29.                 q.push(v);
  30.             }
  31.         }
  32.     }
  33.     return;
  34. }


  37. int main(){
  38.     cin >> n >> m >> sx >> sy;
  39.     memset(field,-1,sizeof(field));
  40.     field[sx][sy] = 0;
  41.     q.push(node(sx,sy));
  42.     bfs();
  43.     for(int i = 1;i <= n;i++){
  44.         for(int j = 1;j <= m;j++)
  45.             printf("%-5d",field[i][j]);
  46.         printf("\n");
  47.     }
  48.     return 0;
  49. }
复制代码


写了个bfs
因为场宽的原因卡了两次
使用iomanip中的setw函数要写在后面，但依旧有迷之错误（有时候会只给四格）
无奈改用%-5d
还有就是头文件里如果不写cstdio的话本地可以过编译但洛谷过不了...
作者: 张笑宇    时间: 2018-6-7 23:34
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int n,m,x,y,i,j,k;
  5. const int mx=100010;
  6. const int mm=410;
  7. int px[mx],py[mx],a[mm][mm];
  8. int fx[8]= {2,-2,2,-2,-1,1,-1,1};
  9. int fy[8]= {1,1,-1,-1,2,2,-2,-2};
  10. int head,tail;
  11. int main()
  12. {
  13.     cin>>n>>m>>x>>y;
  14.     for (i=1; i<=n; i++)
  15.         for (j=1; j<=m; j++) a[i][j]=-1;
  16.     a[x][y]=0;
  17.     head=1,tail=2;
  18.     px[1]=x,py[1]=y;
  19.     while (head!=tail)
  20.     {
  21.         int nx=px[head];
  22.         int ny=py[head];///现在
  23.         for (k=0; k<=7; k++)
  24.         {
  25.             int tx=nx+fx[k];
  26.             int ty=ny+fy[k];///下一步
  27.             if (tx < 1 || tx > n || ty < 1 || ty > m || (a[tx][ty]<=a[nx][ny]+1&&a[tx][ty]+1))
  28.                 continue;
  29.             a[tx][ty]=a[nx][ny]+1;
  30.             px[tail]=tx;
  31.             py[tail]=ty;
  32.             tail++;
  33.         }
  34.         head++;
  35.     }
  36.     for (i=1; i<=n; i++)
  37.     {
  38.         for (j=1; j<=m; j++)
  39.         {
  40.             cout<<left<<setw(5)<<a[i][j];
  41.         }
  42.         cout<<endl;
  43.     }
  44.     return 0;
  45. }
复制代码
作者: 胡雨菲菲    时间: 2018-6-8 10:55
  1. #include <cstdio>
  2. #include <cstring>
  3. using namespace std;
  4. const int N = 410;

  6. int m,n,xx,yy, a[N][N], vis[N][N];
  7. int p[N * N][2],top,tail=1;

  9. int dx[8]={-2,-1,1,2,+2,+1,-1,-2};
  10. int dy[8]={+1,+2,2,1,-1,-2,-2,-1};

  12. void bfs(int x,int y)
  13. {
  14.     for(int i=0;i<=7;i++)
  15.     {
  16.         int nowx=x+dx[i];
  17.         int nowy=y+dy[i];
  18.         if(nowx<1 || nowy<1 || nowx>n || nowy>m) continue;
  19.         if(vis[nowx][nowy]) continue;
  20.         vis[nowx][nowy]=1;
  21.         a[nowx][nowy]=a[x][y]+1;
  22.         top++;
  23.         p[top][0]=nowx;
  24.         p[top][1] = nowy;
  25.     }
  26.     if(tail>top) return;
  27.     tail++;
  28.     bfs(p[tail-1][0],p[tail-1][1]);
  29.     return;
  30. }

  32. int main()
  33. {
  34.     memset (a,-1,sizeof(a));
  35.     scanf ("%d%d%d%d",&n,&m,&xx,&yy);
  36.     vis[xx][yy]=1;
  37.     a[xx][yy]=0;
  38.     bfs(xx,yy);

  40.     for(int i=1;i<=n;i++)
  41.     {
  42.         for(int j=1;j<=m;j++) printf("%-5d",a[i][j]);
  43.         printf("\n");
  44.     }

  46.     return 0;
  47. }
复制代码
作者: 黄煦喆    时间: 2018-6-9 19:13
  1. #include<iostream>
  2. #include<queue>
  3. #include<cstdio>
  4. using namespace std;
  5. int m,n,ix,iy;
  6. struct st
  7. {
  8.     int step;
  9.     int x,y;
  10. } f[410][410];
  11. queue<st>q;
  12. int tx[9]= {0,+1,+1,-1,-1,+2,+2,-2,-2};
  13. int ty[9]= {0,+2,-2,+2,-2,+1,-1,+1,-1};
  14. int main()
  15. {
  16.     cin>>m>>n>>ix>>iy;
  17.     for(int i=1; i<=m; i++)
  18.         for(int j=1; j<=n; j++)
  19.         {
  20.             f[i][j].step=-1;
  21.             f[i][j].x=i;
  22.             f[i][j].y=j;
  23.         }
  24.     f[ix][iy].step=0;q.push(f[ix][iy]);
  25.     while(q.size())
  26.     {
  27.         st t=q.front();
  28.         q.pop();
  29.         for(int i=1; i<=8; i++)
  30.         {
  31.             int fx=t.x+tx[i];
  32.             int fy=t.y+ty[i];
  33.             if(fx>=1&&fx<=m&&fy>=1&&fy<=n&&f[fx][fy].step==-1)
  34.             {
  35.                 f[fx][fy].step=t.step+1;
  36.                 q.push(f[fx][fy]);
  37.             }
  38.         }
  39.     }
  40.     for(int i=1; i<=m; i++)
  41.     {
  42.         for(int j=1; j<=n; j++)
  43.             printf("%-5d",f[i][j].step);
  44.         cout<<endl;
  45.     }
  46.     return 0;
  47. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-8-20 11:03
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. struct node
  5. {
  6.     int r,c,step;
  7. } b[100000];
  8. int n,m,a[410][410],mr,mc,dr[8]= {-2,-2,-1,+1,+2,+2,+1,-1},dc[8]= {-1,+1,+2,+2,+1,-1,-2,-2};
  9. int main()
  10. {
  11.     cin>>n>>m;
  12.     cin>>mr>>mc;
  13.     for(int i=1; i<=n; i++)
  14.         for(int j=1; j<=m; j++)
  15.             a[i][j]=-1;
  16.     int head=0,tail=1;
  17.     b[head].r=mr;
  18.     b[head].c=mc;
  19.     b[head].step=0;
  20.     a[mr][mc]=0;
  21.     while(head<tail)
  22.     {
  23.         for(int i=0; i<=7; i++)
  24.             if(a[b[head].r+dr[i]][b[head].c+dc[i]]==-1 && b[head].r+dr[i]>=1 && b[head].r+dr[i]<=n && b[head].c+dc[i]>=1 && b[head].c+dc[i]<=m)
  25.             {
  26.                 b[tail].r=b[head].r+dr[i];
  27.                 b[tail].c=b[head].c+dc[i];
  28.                 b[tail].step=b[head].step+1;
  29.                 a[b[head].r+dr[i]][b[head].c+dc[i]]=b[tail].step;
  30.                 tail++;
  31.             }
  32.         head++;
  33.     }
  34.     for(int i=1;i<=n;i++)
  35.     {
  36.         for(int j=1;j<=m;j++)
  37.         cout<<left<<setw(5)<<a[i][j];///之前提交4、5次全wa，才发现是左对齐输出。。
  38.         cout<<endl;
  39.     }
  40.     return 0;
  41. }
复制代码
作者: universehyf    时间: 2018-9-1 22:09
//与闻子安一样的情况，特别感谢wza同学的说明，祝百年好合
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int s[410][410];
  5. bool b[410][410];
  6. int q[169000][3];
  7. int dx[8]={-2,-1,1,2,2,1,-1,-2},
  8.     dy[8]={1,2,2,1,-1,-2,-2,-1};
  9. int n,m,r,c,x,y,head,tail,t=-1;
  10. int main()
  11. {
  12.     cin>>n>>m>>r>>c;
  13.     head=0;tail=1;
  14.     q[1][1]=r;q[1][2]=c;q[1][3]=0;
  15.     b[r][c]=1;s[r][c]=0;
  16.     do
  17.     {
  18.         head++;x=q[head][1];y=q[head][2];
  19.         for(int i=0;i<=7;i++)
  20.             if(x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&(!b[x+dx[i]][y+dy[i]]))
  21.             {
  22.                 tail++;b[x+dx[i]][y+dy[i]]=1;
  23.                 q[tail][1]=x+dx[i];q[tail][2]=y+dy[i];q[tail][3]=q[head][3]+1;
  24.                 s[q[tail][1]][q[tail][2]]=q[tail][3];
  25.             }
  26.     }while(head<tail);
  27.     for(int i=1;i<=n;i++)
  28.     {
  29.         for(int j=1;j<=m;j++)
  30.         {
  31.             if(b[i][j]) cout<<left<<setw(5)<<s[i][j];
  32.             else cout<<left<<setw(5)<<t;
  33.         }
  34.         if(i!=n) cout<<endl;
  35.     }
  36.     return 0;
  37. }
复制代码
作者: type尧    时间: 2018-11-4 18:54
  1. //
  2. #include<iostream>
  3. #include<queue>
  4. #include<algorithm>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<iomanip>
  8. #define maxn 201
  9. using namespace std;
  10. typedef int h;
  11. h martix[maxn][maxn];
  12. h n,m,move[8][2]={{-2,+1},{-1,+2},{+1,+2},{+2,+1},{+2,-1},{+1,-2},{-1,-2},{-2,-1}};
  13. struct point{
  14.         h x,y,n;
  15. }p;
  16. queue<point> q;
  17. void getdata()
  18. {
  19.         cin>>n>>m;
  20.         for(h i=1;i<=n;i++)
  21.                 for(h j=1;j<=m;j++)
  22.                         martix[i][j]=-1;
  23.         cin>>p.x>>p.y;
  24.         return;
  25. }
  26. void bfs()
  27. {
  28.         martix[p.x][p.y]=0;
  29.         q.push(p);
  30.         while(!q.empty()){
  31.                 point temp;
  32.                 for(h i=0;i<8;i++){
  33.                         temp=q.front();
  34.                         h x=temp.x+move[i][0];
  35.                         h y=temp.y+move[i][1];
  36.                         if(x<1||x>n||y<1||y>m||martix[x][y]!=-1) continue;
  37.                         temp.x+=move[i][0];
  38.                         temp.y+=move[i][1];
  39.                         temp.n++;
  40.                         q.push(temp);
  41.                         martix[temp.x][temp.y]=temp.n;
  42.                 }
  43.                 q.pop();
  44.         }
  45.         return;
  46. }
  47. void print()
  48. {
  49.         for(h i=1;i<=n;i++){
  50.                 for(h j=1;j<=m;j++)
  51.                         cout<<setiosflags(ios::left)<<setw(5)<<martix[i][j];
  52.                 cout<<endl;       
  53.         }
  54. }
  55. h main()
  56. {
  57.         getdata();
  58.         bfs();
  59.         print();
  60.         return 0;
  61. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2