记录编号	553794	评测结果	AAAAAAAAAA
题目名称	3031.[CH 2906]骑士风度的牛	最终得分	100
用户昵称	城南花已开	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-08-25 22:14:39	内存使用	0.00 MiB

# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
char farm1[151][151];
int c,r,startx,starty,finishx,finishy,qx[22501],qy[22501];
int heng[9]={0,1,2,2,1,-1,-2,-2,-1},shu[9]={0,2,1,-1,-2,-2,-1,1,2},deep[22501];
int bfs(){
	int head=0,tail=1,i;
	qx[1]=startx;
	qy[1]=starty;
	deep[1]=0;
	do{
		head++;
		for(i=1;i<=8;i++){
			if(qx[head]+heng[i]>=1&&qx[head]+heng[i]<=r&&qy[head]+shu[i]>=1&&qy[head]+shu[i]<=c){
			    if(farm1[qx[head]+heng[i]][qy[head]+shu[i]]=='.'){
			    	tail++;
			    	deep[tail]=deep[head]+1;
			    	qx[tail]=qx[head]+heng[i];
			    	qy[tail]=qy[head]+shu[i];
			    	farm1[qx[tail]][qy[tail]]='*';
			    	if(qx[tail]==finishx&&qy[tail]==finishy){
			    		cout <<deep[tail];
			    		head=tail;
                        break;
					}
				}
			}
		}
	}while(head<tail);
}
int main(){
	freopen("warrior_cow.in","r",stdin);
	freopen("warrior_cow.out","w",stdout);
	scanf("%d%d",&c,&r);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >>farm1[i][j];
            if(farm1[i][j]=='K'){
            	startx=i;
            	starty=j;
			}
			if(farm1[i][j]=='H'){
				finishx=i;
				finishy=j;
				farm1[i][j]='.';
			}
        }
    }
    bfs();
    fclose(stdin);
    fclose(stdout);
    return 0;
}