Poj 2329 Nearest number - 2 이거 광수인데 왜 wa야!!해답을 구하다

3472 단어
              dp          !!  0         ,     ,          
          wa !!  discuss           wa       !!!
       wa   !!!           !!!
 #include<iostream>
 #include<queue>
 using namespace std;
 int a[205][205],b[205][205],sign[205][205];
 #define doit(n) for(int i=1;i<=n;i++)
 #define doitj(n) for(int j=1;j<=n;j++)
 int ads(int x,int y)
 {
        if(x-y>0)
        return x-y;
        return y-x;
}
 int dir[8][2]={0,1,1,0,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};    
 int s;
 queue<int>q ;
 void bfs(int x,int y)
 {
        int temp=0x7FFFFFFF;
        int dis;
        q.push(x);
        q.push(y);
        while(!q.empty())
        {
            int m=q.front();q.pop();
            int n=q.front();q.pop();
            for(int i=0;i<8;i++)
            {
                int mm=m+dir[i][1];
                int nn=n+dir[i][0];              
                if(mm>=1&&mm<=s&&nn>=1&&nn<=s&&sign[mm][nn]==0)
                {      
                    sign[mm][nn]=1;
                    q.push(mm);
                    q.push(nn);
                    if(a[mm][nn]!=0)
                    {
                        dis=ads(mm,x)+ads(nn,y);
                        if(dis<temp)
                        {        
                            temp=dis;
                            b[x][y]=a[mm][nn];                          
                        }
                        else if(dis==temp)
                        {
                            b[x][y]=0;
                            while(!q.empty())
                            q.pop();
                            break;
                        }
                        if(dis>temp+2)
                        {
                            while(!q.empty())
                            q.pop();
                            break;
                        }
                            
                    }
                        
                }
            }
        
    }  
}     
 int main()
 {
       
        while(scanf("%d",&s)!=EOF)
        {
            doit(s)
            {
                doitj(s)
                {
                    scanf("%d",&a[i][j]);
                    b[i][j]=a[i][j];
                }
            }
            doit(s)
            {
                doitj(s)
                if(a[i][j]==0)
                {
                    memset(sign,0,sizeof(sign));
                    bfs(i,j);
                }
            }
            doit(s)
            {
                doitj(s)
                {
                    if(j==s)
                    printf("%d
",b[i][j]); else printf("%d ",b[i][j]); } } } return 0; }

좋은 웹페이지 즐겨찾기