5 4XXXXXX   XXXX X XXX 2 3 5 31 3 4 42 3 3 40 0 0 00 0Sample Output
Board #1:Pair 1: 4 segments.Pair 2: 3 segments.Pair 3: impossible.
解題報(bào)告
直接廣搜就行了，由隊(duì)列的每個(gè)點(diǎn)向四個(gè)方向標(biāo)記直到遇到'X'，小心每組結(jié)束還有個(gè)/n,
#include<stdio.h>#include<string.h>#include<queue>#define MAX_N 80#define INF 0x3f3f3f3fusing namespace std;char map[MAX_N][MAX_N];int dp[MAX_N][MAX_N];const int ox[]={0,0,1,-1};const int oy[]={1,-1,0,0};int w,h;int s_x,s_y,e_x,e_y;int bfs(){    memset(dp,0x3f,sizeof(dp));    queue<pair<int,int> > que;    que.push(make_pair(s_x,s_y));    dp[s_y][s_x]=0;    map[e_y][e_x]=' ';    int H=h+1,W=w+1;        while(!que.empty()){        int X=que.front().first,Y=que.front().second;que.pop();        int S=dp[Y][X]+1;        for(int i=0;i<4;i++){            int x=X,y=Y;            while(true){                x+=ox[i],y+=oy[i];                if(x<0||x>W||y<0||y>H||map[y][x]=='X') break;                if(dp[y][x]<=S) continue;                que.push(make_pair(x,y));                dp[y][x]=S;            }        }    }    map[e_y][e_x]='X';    return dp[e_y][e_x];}int main(){    int Board=1,Pair;    while(~scanf("%d%d",&w,&h)&&w&&h){        memset(map,0,sizeof(map));        getchar();        for(int i=1;i<=h;i++)            gets(map[i]+1);        printf("Board #%d:/n",Board++);Pair=1;        while(scanf("%d%d%d%d",&s_x,&s_y,&e_x,&e_y)&&s_x&&s_y&&e_x&&e_y){            printf("Pair %d: ",Pair++);            int ans=bfs();            if(ans==INF) puts("impossible.");            else printf("%d segments./n",ans);        }        putchar('/n');    }    return 0;}