P1443 马的遍历
2018-06-17 22:36:52来源:未知 阅读 ()
题目描述
有一个n*m的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入输出格式
输入格式:一行四个数据,棋盘的大小和马的坐标
输出格式:一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)
输入输出样例
3 3 1 1
0 3 2 3 -1 1 2 1 4
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=501; 8 int map[MAXN][MAXN]; 9 int n,m,bgx,bgy; 10 int xx[9]={-2,-1,+1,+2,+2,+1,-1,-2}; 11 int yy[9]={-1,-2,-2,-1,+1,+2,+2,+1}; 12 struct node 13 { 14 int x,y,step; 15 }cur,nxt; 16 void bfs() 17 { 18 cur.x=bgx;cur.y=bgy;cur.step=0; 19 queue<node>q; 20 q.push(cur); 21 while(q.size()!=0) 22 { 23 node p=q.front(); 24 q.pop(); 25 for(int i=0;i<8;i++) 26 { 27 node nxt; 28 nxt.x=p.x+xx[i]; 29 nxt.y=p.y+yy[i]; 30 nxt.step=p.step+1; 31 if(nxt.x>=1&&nxt.x<=n&&nxt.y>=1&&nxt.y<=m&&map[nxt.x][nxt.y]==-1) 32 { 33 map[nxt.x][nxt.y]=nxt.step; 34 q.push(nxt); 35 } 36 } 37 } 38 } 39 int main() 40 { 41 scanf("%d%d%d%d",&n,&m,&bgx,&bgy); 42 for(int i=1;i<=n;i++) 43 for(int j=1;j<=m;j++) 44 map[i][j]=-1; 45 map[bgx][bgy]=0; 46 bfs(); 47 for(int i=1;i<=n;i++) 48 { 49 for(int j=1;j<=m;j++) 50 { 51 printf("%-5d",map[i][j]); 52 } 53 printf("\n"); 54 } 55 return 0; 56 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash