思路： 每個地方能走多次 所以得記錄狀態 把大明記為1 二明記為2所以狀態裡最多有4種狀態（0，1，2，3） 對每一點 每個狀態只能走一次 判斷能不能看到 直接根據坐標判斷 如果x相等 判斷之間有沒有牆和人 其他思路同一般廣搜
#include#include #include #include using namespace std; int n,m,mark[110][110][10]; char map[110][110]; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int dx,dy,ex,ey,tt; struct node { int x,y; int step; int state; }a,b; int min(int x,int y) { return x<y?x:y; } int max(int x,int y) { return x>y?x:y; } int judge(node p) { int i,j; int cont=0; int flash=0; if(p.x==dx) { for(i=min(p.y,dy)+1;i<max(p.y,dy);i++) { if(map[dx][i]=='X'||dx==ex&&i==ey) {flash=1;break;} } if(flash==0) cont+=map[dx][dy]-'0'; } flash=0; if(p.y==dy) { for(i=min(p.x,dx)+1;i<max(p.x,dx);i++) { if(map[i][dy]=='X'||dy==ey&&i==ex) { flash=1; break; } } if(flash==0) cont+=map[dx][dy]-'0'; } flash=0; if(p.x==ex) { for(i=min(p.y,ey)+1;i<max(p.y,ey);i++) { if(map[ex][i]=='X'||ex==dx&&i==dy) {flash=1;break;} } if(flash==0) cont+=map[ex][ey]-'0'; } flash=0; if(p.y==ey) { for(i=min(p.x,ex)+1;i<max(p.x,ex);i++) { if(map[i][ey]=='X'||ey==dy&&i==dx) { flash=1; break; } } if(flash==0) cont+=map[ex][ey]-'0'; } return cont; } int bfs(int xi,int xj) { int i; memset(mark,0,sizeof(mark)); a.x=xi; a.y=xj; a.state=judge(a); a.step=0; queue<node>q; mark[a.x][a.y][a.state]=1; q.push(a); int flash=0; while(!q.empty()) { b=q.front(); q.pop(); if(b.state==3) { flash=1; printf("%d\n",b.step); break; } for(i=0;i<4;i++) { a.x=b.x+dir[i][0]; a.y=b.y+dir[i][1]; a.step=b.step+1; if(a.x<0||a.x>=n||a.y<0||a.y>=m) continue; if(map[a.x][a.y]=='1'||map[a.x][a.y]=='2') continue; if(map[a.x][a.y]=='X') continue; if(a.step>tt) continue; a.state=b.state; int t=judge(a); if(t==3) a.state=t; else if(t==2) { if(a.state!=2) a.state+=t; } else if(t==1) { if(a.state!=1) a.state+=t; } if(mark[a.x][a.y][a.state]==0) { mark[a.x][a.y][a.state]=1; q.push(a); } } } if(flash==0) printf("-1\n"); return 0; } int main() { int i,j,T,d=1; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&tt); for(i=0;i<n;i++) scanf("%s",map[i]); int xi,xj; for(i=0;i<n;i++) for(j=0;j<m;j++) { if(map[i][j]=='D') { map[i][j]='1'; dx=i; dy=j; } else if(map[i][j]=='E') { map[i][j]='2'; ex=i; ey=j; } else if(map[i][j]=='S') { xi=i; xj=j; } } //printf("%d^^^^%d\n",xi,xj); printf("Case %d:\n",d++); bfs(xi,xj); } return 0; }
