loj 1055(bfs)

タイトルリンク:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26772
考え方:重さを判断することに注意して、6次元配列を開いて3つのrobotsの位置を記録して、それから注意しなければならないのは複数のrobotsが同時に1つの格子の上で、最初はこの点に気づかなかったことです!

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<queue>

 6 using namespace std;

 7 #define MAXN 11

 8 

 9 struct Point{

10     int x,y;

11 };

12 

13 struct Node{

14     Point p[3];

15     int step;

16 }st;

17 

18 char map[MAXN][MAXN];

19 bool mark[MAXN][MAXN][MAXN][MAXN][MAXN][MAXN];

20 int n,dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

21 

22 void bfs()

23 {

24     memset(mark,false,sizeof(mark));

25     queue<Node>que;

26     st.step=0;

27     que.push(st);

28     mark[st.p[0].x][st.p[0].y][st.p[1].x][st.p[1].y][st.p[2].x][st.p[2].y]=true;

29     while(!que.empty()){

30         Node q,pp=que.front();

31         que.pop();

32         if(map[pp.p[0].x][pp.p[0].y]=='X'&&map[pp.p[1].x][pp.p[1].y]=='X'&&map[pp.p[2].x][pp.p[2].y]=='X'){

33             printf("%d
",pp.step);

34             return ;

35         }

36         for(int i=0;i<4;i++){

37             for(int j=0;j<=2;j++){

38                 q.p[j].x=pp.p[j].x+dir[i][0],q.p[j].y=pp.p[j].y+dir[i][1];

39                 if(q.p[j].x<0||q.p[j].x>=n||q.p[j].y<0||q.p[j].y>=n){

40                     q.p[j].x=pp.p[j].x,q.p[j].y=pp.p[j].y;

41                 }else if(map[q.p[j].x][q.p[j].y]=='#'){

42                     q.p[j].x=pp.p[j].x,q.p[j].y=pp.p[j].y;

43                 }

44             }

45             //robots         

46             for(int l=0;l<=2;l++){

47                 for(int j=0;j<=2;j++){

48                     for(int k=0;k<=2;k++)if(j!=k){

49                         if(q.p[j].x==q.p[k].x&&q.p[j].y==q.p[k].y)q.p[j].x=pp.p[j].x,q.p[j].y=pp.p[j].y;

50                     }

51                 }

52             }

53             if(!mark[q.p[0].x][q.p[0].y][q.p[1].x][q.p[1].y][q.p[2].x][q.p[2].y]){

54                 mark[q.p[0].x][q.p[0].y][q.p[1].x][q.p[1].y][q.p[2].x][q.p[2].y]=true;

55                 q.step=pp.step+1;

56                 que.push(q);

57             }

58         }

59     }

60     puts("trapped");

61 }

62 

63 

64 int main()

65 {

66     int _case,num,t=1;

67     scanf("%d",&_case);

68     while(_case--){

69         scanf("%d",&n);

70         num=0;

71         for(int i=0;i<n;i++){

72             scanf("%s",map[i]);

73             for(int j=0;j<n;j++){

74                 if(map[i][j]=='A'||map[i][j]=='B'||map[i][j]=='C'){

75                     st.p[num].x=i,st.p[num].y=j;

76                     num++;

77                 }

78             }

79         }

80         printf("Case %d: ",t++);

81         bfs();

82     }

83     return 0;

84 }

View Code