2723 - 雯神与狗不得不说的故事1
众所周知雯神特别怕狗，所以雯神在走路的时候都不敢走有狗的地方（雯神所在位置不能和狗重叠），现在雯神要从一个地方走到另外一个地方，但是路途中有一些狗，并且这些狗是会移动的，雯神赶时间，但是雯神又怕狗，所以请帮帮雯神，狗的移动方式为（上，右，下，左）题目保证最上方和最右边的初始位置没有狗。（雯神可在原地等待）
Input
多组输入，每组输入一个n和一个m(1<=n,m<=10)表示矩阵的行和列，接下来输入一个n*m的矩阵
"D"表示狗初始位置,"S"表示雯神的起始位置，"E"表示雯神要去的终点.
Output
如果雯神能到达输出最小步数，否则输出"kill the dog,god wen!"
Examples
Input
3 3 S.. .D. ..E 4 4 S... .... ..D. .D.E
Output
4 6
Solution C++
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<iostream> using namespace std; struct P { int x,y; int time; }; bool map[15][15][4]; char a[15][15]; bool vis[15][15][4]; int x[4]={1,0,-1,0}; int y[4]={0,1,0,-1}; int n,m; int bfs(P s,P e) { queue<P> q; q.push(s); vis[s.x][s.y][s.time]=1; bool flag=0; while(!q.empty()) { P p=q.front(); q.pop(); //printf("%d-%d-%d\n",p.x,p.y,p.time); if(p.x==e.x&&p.y==e.y) return p.time; for(int i=0;i<4;i++) { int nx=p.x+x[i]; int ny=p.y+y[i]; if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny][(p.time+1)%4]&&!map[nx][ny][(p.time+1)%4]) { vis[nx][ny][(p.time+1)%4]=1; P p1; p1.x=nx;p1.y=ny;p1.time=p.time+1; q.push(p1); } } int time=p.time+1; if(!map[p.x][p.y][(time)%4]&&!vis[p.x][p.y][(time)%4]) { p.time++; q.push(p); } } return -1; } int main() { //freopen("F input.txt","r",stdin); //freopen("F output.txt","w",stdout); while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%s",a[i]); P s,e; memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]=='S') { s.x=i; s.y=j; s.time=0; } else if(a[i][j]=='E') { e.x=i; e.y=j; } else if(a[i][j]=='D') { map[i][j][0]=1; map[i-1][j][1]=1; map[i-1][j+1][2]=1; map[i][j+1][3]=1; } } } int k=0; k=bfs(s,e); if(k!=-1) printf("%d\n",k); else printf("kill the dog,god wen!\n"); } }