P1443 马的遍历

admin

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

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

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. }
    
35. 
    
36. 
    
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的话本地可以过编译但洛谷过不了...

张笑宇

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. }
    

复制代码

胡雨菲菲

1. #include <cstdio>
   
2. #include <cstring>
   
3. using namespace std;
   
4. const int N = 410;
   
5. 
   
6. int m,n,xx,yy, a[N][N], vis[N][N];
   
7. int p[N * N][2],top,tail=1;
   
8. 
   
9. int dx[8]={-2,-1,1,2,+2,+1,-1,-2};
   
10. int dy[8]={+1,+2,2,1,-1,-2,-2,-1};
    
11. 
    
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. }
    
31. 
    
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);
    
39. 
    
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.     }
    
45. 
    
46.     return 0;
    
47. }
    

复制代码

黄煦喆

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. }
    

复制代码

倚窗倾听风吹雨

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

//与闻子安一样的情况，特别感谢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尧

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. }
    

复制代码