jzoj 2044. 死者之魂推动遇难船

lzusa 发布于 2019-03-30 1 次阅读


 

题目只有图片。。。。。。
思路
每条边进行判断然后跑一边bfs
#include 
#include 
using namespace std;
int f[1002][1002];
int x[1000000],y[1000000];
int n,m,h,s;
__attribute__((optimize("O2")))
int bfs()
{
    int head=0,tail=s+1,i,j;
    while (head<=tail)
    {
        head++;
        if (f[x[head]+1][y[head]]==0&&x[head]+1>n-h&&x[head]+1<=n)
            {
                tail++;
                x[tail]=x[head]+1;
                y[tail]=y[head];
                f[x[tail]][y[tail]]=2;
            }
        if (f[x[head]][y[head]+1]==0&&x[head]>n-h&&y[head]+1<=m)
            {
                tail++;
                x[tail]=x[head];
                y[tail]=y[head]+1;
                f[x[tail]][y[tail]]=2;
            }
        if (f[x[head]-1][y[head]]==0&&x[head]-1>n-h&&x[head]-1>=1)
            {
                tail++;
                x[tail]=x[head]-1;
                y[tail]=y[head];
                f[x[tail]][y[tail]]=2;
            }
        if (f[x[head]][y[head]-1]==0&&x[head]>n-h&&y[head]-1>=1)
            {
                tail++;
                x[tail]=x[head];
                y[tail]=y[head]-1;
                f[x[tail]][y[tail]]=2;
            }    
    } 
    return 0;
};
__attribute__((optimize("O2")))
int main()
{ 
    freopen("cruise.in","r",stdin);
    freopen("cruise.out","w",stdout);
   // memset(f,100000,sizeof(f));
    char ch[1050];
    int i,j,k;
    scanf("%d%d%d",&n,&m,&h);
    for (i=1;i<=n;i++)
    {
        scanf("%s",&ch);
        for (j=1;j<=m;j++)
        {
        
            f[i][j]=int(ch[j-1])-48;
        }
    }
    s=0;
    
    for (i=1;i<=m;i++)
        if (f[1][i]==0&&1>n-h)
            {
                s++;
                x[s]=1;
                y[s]=i;
                f[1][i]=2;
            }
    for (i=1;i<=m;i++)
        if (f[n][i]==0&&n>n-h)
            {
                s++;
                x[s]=n;
                y[s]=i;
                f[n][i]=2;
            }
    for (i=1;i<=n;i++)
        if (f[i][1]==0&&i>n-h)
            {
                s++;
                x[s]=i;
                y[s]=1;
                f[i][1]=2;
            }
    for (i=1;i<=n;i++)
        if (f[i][m]==0&&i>n-h)
            {
                s++;
                x[s]=i;
                y[s]=m;
                f[i][m]=2;
            }
            
   bfs();
   for (i=1;i<=n;i++)
   {
        for (j=1;j<=m;j++)
        { 
            printf("%d",f[i][j]);
        }
        printf("\n");
   }
   return 0;
}

 

]]>