题解 | #格点上的芯片#

一道简单的bfs搜索题，bfs最早搜到终点的那条路径一定是最短的路径，输出步数即可，然后就是搜过的点没有必要再搜了，既然曾经被走过，那么再重复走这点的路径肯定不是最短路，再次重新走也是多余。

#include<bits/stdc++.h>
using namespace std;
int x,y;
struct node{
	int x,y;
	node(int a,int b){
		x=a; y=b;
	}
	node(){
	}
};

bool check(int xx,int yy,int tx,int ty){
	double ans=sqrt((xx-tx)*(xx-tx)+(yy-ty)*(yy-ty));
	int p=ans;
	if(ans-p==0){
		return true;
	}
	return false;
}
int step[60][60];
int vis[60][60];
void bfs(int xx,int yy){
	queue<node> q;
	vis[xx][yy]=1;
	q.push(node(xx,yy));
	while(!q.empty()){
		node tmp=q.front();
		if(tmp.x==x&&tmp.y==y){
			cout<<step[tmp.x][tmp.y]<<endl;
			return;
		}
		q.pop();
		for(int i=tmp.x;i<=x;i++){
			for(int j=tmp.y;j<=y;j++){
				if(check(i,j,tmp.x,tmp.y)&&!vis[i][j]){
					vis[i][j]=1;
					step[i][j]=step[tmp.x][tmp.y]+1;
					q.push(node(i,j));
				}
				
			}
		}
	}
}

int main(){
	int t;
	cin>>t;
	while(t--){
		memset(step,0,sizeof(step));
		memset(vis,0,sizeof(vis));
		cin>>x>>y;
		bfs(0,0);
	}
}