PKU1915 Knight Moves
300*300までの正方形のチェス盤的なものにナイトを置く。
何回でゴールまでたどり着けるか
小さいしBFSでいける。
というか今日BFSばっかりやってる気がする。
DPやらなきゃまずいんじゃないの?
#include<stdio.h> #include<queue> #include<algorithm> #include<math.h> using namespace std; int kx[]={-2,-2,-1,-1,1,1,2,2}; int ky[]={1,-1,2,-2,2,-2,1,-1}; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ int table[300][300]; int l; scanf("%d",&l); for(int j=0;j<l;j++) for(int k=0;k<l;k++) table[j][k]=-1; queue <pair<int,int> > Q; int sx,sy; scanf("%d%d",&sx,&sy); table[sx][sy]=0; int gx,gy; scanf("%d%d",&gx,&gy); Q.push(make_pair(sx,sy)); while(Q.size()){ int nowx=Q.front().first; int nowy=Q.front().second; //printf("%d %d\n",nowx,nowy); for(int j=0;j<8;j++) if(nowx+kx[j]>=0&&nowx+kx[j]<l&&nowy+ky[j]>=0&&nowy+ky[j]<l&&table[nowx+kx[j]][nowy+ky[j]]==-1){ table[nowx+kx[j]][nowy+ky[j]]=table[nowx][nowy]+1; Q.push(make_pair(nowx+kx[j],nowy+ky[j])); } Q.pop(); } printf("%d\n",table[gx][gy]); } }