栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 1505 Solitaire

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 1505 Solitaire

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#include <map>#include <vector>using namespace std;#define N 8 int g[N][N];int godir[][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};int gtoi (int a[][N]) {int rs = 0;int loc = 10000000;for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {if (a[i][j]==1) {rs += i*loc;loc /= 10;rs += j*loc;loc /= 10;}if(loc==1) break;}if(loc==1) break;}return rs;}void itog(int a[][N], int st) {for(int i = 0; i < N; ++i) memset(a[i], 0, sizeof(a[i]));int loc = 10000000;int x,y;for (int i = 0; i < 4; ++i) {x = st/loc%10;loc /= 10;y = st/loc%10;loc /= 10;a[x][y] = 1;}}void show(int a[][N]) {for(int i = 0; i < N; ++i) {for(int j = 0; j < N; ++j) printf("%d",a[i][j]);puts("");}puts("");}void show(int sta) {int a[N][N];itog(a, sta);show(a);}int findadj (vector<int> &adj, const int fr) {adj.clear();int tmp[N][N];int ball[4][2];int loc = 10000000;for (int i = 0; i < 4; ++i) {ball[i][0] = fr/loc%10;loc /= 10;ball[i][1] = fr/loc%10;loc /= 10;}for(int i = 0; i < 4; ++i) {for(int j = 0; j < 4; ++j) {itog(tmp, fr);int x = ball[i][0] + godir[j][0];int y = ball[i][1] + godir[j][1];int flag = 1;if( 0 <= x && x < N && 0 <= y && y < N && tmp[x][y]!=1) {flag = 0;tmp[x][y] = 1;tmp[ball[i][0]][ball[i][1]] = 0;adj.push_back( gtoi(tmp) );}if(flag) {x = ball[i][0] + godir[j][0]*2;y = ball[i][1] + godir[j][1]*2;if( 0 <= x && x < N && 0 <= y && y < N && tmp[x][y]!=1) {tmp[x][y] = 1;tmp[ball[i][0]][ball[i][1]] = 0;adj.push_back( gtoi(tmp) );}}}}}int dsbfs(int src, int des) {int dir = 0; int e[2];queue<int> que[2]; map<int, int> dis[2];vector<int> adj; e[0] = des,e[1] = src; que[0].push(src), que[1].push(des);dis[0][src] = 1, dis[1][des] = 1;while(!que[0].empty() || !que[1].empty()) {dir = que[0].size() <= que[1].size() ? 0 : 1; if(que[dir].empty() && !que[!dir].empty()) dir = !dir;  int fr = que[dir].front();que[dir].pop();int frdis = dis[dir][fr];if(e[dir]==fr) { return frdis;}if(dis[!dir][fr]) { return dis[!dir][fr] + frdis - 1;}findadj(adj, fr);for(int i = 0; i < adj.size(); ++i) {if(dis[dir][adj[i]]==0 && frdis + 1 <= 5) { dis[dir][adj[i]] = frdis + 1;que[dir].push(adj[i]);}}}return 0;}int main () {int x, y;int src, des;while(scanf("%d", &x) - EOF) {scanf("%d", &y);memset(g, 0, sizeof(g));g[x-1][y-1] = 1;for (int i = 0; i < 3; ++i) {scanf("%d%d", &x, &y);g[x-1][y-1] = 1;}src = gtoi(g);memset(g, 0, sizeof(g));for (int i = 0; i < 4; ++i) {scanf("%d%d", &x, &y);g[x-1][y-1] = 1;}des = gtoi(g);printf("%sn", dsbfs(src, des)? "YES" : "NO");}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/373482.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号