【题解-信息学奥赛一本通】1330：【例8.3】最少步数

题目1330【例8.3】最少步数题目描述在各种棋中棋子的走法总是一定的如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性因此他规定马既能按“日”走也能如象一样走“田”字。他的同桌平时喜欢下围棋知道这件事后觉得很有趣就想试一试在一个100×100的围棋盘上任选两点A、BA点放上黑子B点放上白子代表两匹马。棋子可以按“日”字走也可以按“田”字走俩人一个走黑马一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时谁获胜。现在他请你帮忙给你A、B两点的坐标想知道两个位置到1,1点可能的最少步数。输入A、B两点的坐标。输出最少步数。时空限制1s / 64MB样例输入12 16 18 10样例输出8 9代码#includebits/stdc.husingnamespacestd;constintN10010;typedefpairint,intPII;intn100,ans,sx,sy,dx[16]{-2,-1,1,2,2,1,-1,-2,-2,2,2,-2},dy[16]{1,2,2,1,-1,-2,-2,-1,2,2,-2,-2};intdis[N][N];voidbfs(intx,inty){queuePIIq;q.push({x,y});dis[x][y]0;while(!q.empty()){PII tq.front();q.pop();for(inti0;i12;i){intxxt.firstdx[i],yyt.seconddy[i];if(xx1||xxn||yy1||yyn)continue;if(dis[xx][yy]-1){q.push({xx,yy});dis[xx][yy]dis[t.first][t.second]1;}}}}intmain(){for(inti0;i2;i){cinsxsy;ans0;memset(dis,-1,sizeofdis);bfs(sx,sy);coutdis[1][1]endl;}return0;}结果