首页 > ACM题库 > HDU-杭电 > hdu 2262 Where is the canteen-BFS-[解题报告]C++
2014
01-04

hdu 2262 Where is the canteen-BFS-[解题报告]C++

Where is the canteen

问题描述 :

After a long drastic struggle with himself, LL decide to go for some snack at last. But when steping out of the dormitory, he found a serious problem : he can’t remember where is the canteen… Even worse is the campus is very dark at night. So, each time he move, he check front, back, left and right to see which of those four adjacent squares are free, and randomly walk to one of the free squares until landing on a canteen.

输入:

Each case begin with two integers n and m ( n<=15,m<=15 ), which indicate the size of the campus. Then n line follow, each contain m characters to describe the map. There are 4 different type of area in the map:

‘@’ is the start location. There is exactly one in each case.
‘#’ is an impassible square.
‘$’ is a canteen. There may be more than one in the campus.
‘.’ is a free square.

输出:

Each case begin with two integers n and m ( n<=15,m<=15 ), which indicate the size of the campus. Then n line follow, each contain m characters to describe the map. There are 4 different type of area in the map:

‘@’ is the start location. There is exactly one in each case.
‘#’ is an impassible square.
‘$’ is a canteen. There may be more than one in the campus.
‘.’ is a free square.

样例输入:

1 2
@$
2 2
@.
.$
1 3
@#$

样例输出:

1.000000
4.000000
-1

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#define eps 1e-8
#define maxn 226
using namespace std;
char s[22][22];
int n,m;
int cnt;
struct node
{
    int x,y;
    node(){};
    node(int xx,int yy){x=xx,y=yy;}
};
node st;
int vis[22][22];
int X[]={0,0,-1,1};
int Y[]={-1,1,0,0};
bool inmap(int x,int y)
{
    if(0<=x&&x<n&&0<=y&&y<m) return true;
    else return false;
}
bool bfs()
{
    int flag=0;
    memset(vis,-1,sizeof(vis));
    queue<node> q;
    cnt=0;
    vis[st.x][st.y]=cnt++;
    q.push(st);
    while(!q.empty())
    {
        node tmp=q.front();q.pop();
        if(s[tmp.x][tmp.y]=='$') flag=1;
        for(int i=0;i<4;i++)
        {
            node next=node(tmp.x+X[i],tmp.y+Y[i]);
            if(!inmap(next.x,next.y)) continue;
            else if(s[next.x][next.y]=='#') continue;
            else if(vis[next.x][next.y]==-1)
            {
                vis[next.x][next.y]=cnt++;
                q.push(next);
            }
        }
    }
    return flag;
}
double A[maxn][maxn];
void build()
{
    memset(A,0,sizeof(A));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(vis[i][j]==-1) continue;
            else if(s[i][j]=='$')
            {
                A[vis[i][j]][vis[i][j]]=1;
                A[vis[i][j]][cnt]=0;
            }
            else
            {
                int nn=0;
                for(int k=0;k<4;k++)
                {
                    node next= node(i+X[k],j+Y[k]);
                    if(!inmap(next.x,next.y)) continue;
                    else if(vis[next.x][next.y]==-1) continue;
                    else if(s[next.x][next.y]=='#') continue;
                    else
                    {
                        A[vis[i][j]][vis[next.x][next.y]]=-1.0;
                        nn++;
                    }
                }
                A[vis[i][j]][vis[i][j]]=nn;
                A[vis[i][j]][cnt]=nn;
            }
        }
    }
}
int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    else return x>0?1:-1;
}
bool gaosi()
{
    int i,j,r,c;
    for(r=0,c=0;r<cnt&&c<cnt;r++,c++)
    {
        //找不是0的行
        for(i=r;i<cnt;i++)
        {
            if(sgn(A[i][c])!=0) break;
        }
        if(i==cnt)
        {
            r--;continue;
        }
        //替换
        if(i!=r)
        {
            for(j=c;j<=cnt;j++) swap(A[i][j],A[r][j]);
        }
        //消元
        for(i=r+1;i<cnt;i++)
        {
            for(j=cnt;j>=c;j--)
            {
                A[i][j]-=A[r][j]/A[r][c]*A[i][c];
            }
        }
    }
    for(i=r;i<cnt;i++)
    {
        if(sgn(A[i][cnt]!=0)) return 1;//无解
    }
    if(r<cnt) return cnt-r;//有无穷解
    //回溯
    for(i=cnt-1;i>=0;i--)
    {
        for(j=cnt-1;j>i;j--)
        {
            A[i][cnt]-=A[i][j]*A[j][cnt];
        }
        A[i][cnt]/=A[i][i];
        A[i][i]=1;
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%s",s[i]);
            for(int j=0;j<m;j++)
            {
                if(s[i][j]=='@')
                {st.x=i,st.y=j;}
            }
        }
        if(!bfs())
        {
            printf("-1\n");
            continue;
        }
        build();
        if(gaosi()!=0)
        {
            printf("-1\n");
        }
        else
        {
            printf("%.6lf\n",A[0][cnt]);
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/qq415200973/article/details/12850425


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。