joj2410: The knight problem
2023-03-14 10:17:21 时间
#include<iostream> #include<cstdio> #include<queue> using namespace std; typedef struct Point { int x, y; }POINT; queue <POINT> me; POINT Begin , End; bool visited[9][9]; bool flag; int ans; int movei[8]= {2,-2,1,-1,2,-2,1,-1}; int movej[8]= {1,-1,2,-2,-1,1,-2,2}; void init() { int i, j; for(i = 0; i < 9; i++) for(j = 0; j < 9; j++) visited[i][j] = false; } bool isok(POINT *p) { if(p->x == End.x && p->y == End.y) return true; else return false; } bool isin(POINT *pt) { if(pt->x >= 1 && pt->x <= 8) if(pt->y >= 1 && pt->y <= 8) return true; return false; } void change(char *str, POINT *pt) { pt->x = str[0] - 'a' +1; pt->y =str[1] - '0'; } void bfs() { int i, q, casenum; POINT pt, tp; casenum = 1; while(!me.empty()) { ans++; q = 0; while(casenum--) { pt = me.front(); me.pop(); for( i = 0; i < 8; i++) { tp.x = pt.x + movei[i]; tp.y = pt.y + movej[i]; if(isin(&tp)) { if(visited[tp.x][tp.y]) continue; else { if(isok(&tp)) { flag = true; return; } else { visited[tp.x][tp.y] = true; me.push(tp); q++; } } } } } casenum = q; } if(me.empty()) flag = false; return ; } int main() { int n, i, casenum; POINT tp; char str[10]; casenum = 1; while(true) { while(!me.empty()) me.pop(); flag = true; ans = 0; init(); scanf("%d", &n); if(-1 == n) break; for(i = 0; i < n; i++) { scanf("%s", str); change(str, &tp); visited[tp.x][tp.y] = true; } scanf("%s", str); change(str, &Begin); scanf("%s", str); change(str, &End); me.push(Begin); visited[Begin.x][Begin.y] = true; if(isok(&Begin)) printf("Board %d: %d moves\n", casenum, ans); bfs(); if(flag) printf("Board %d: %d moves\n", casenum, ans); else printf("Board %d: not reachable\n", casenum); casenum++; } return 0; }题目链接
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的