[NewTrain 10][poj 2329]Nearest Number

题面：

http://poj.org/problem?id=2329

题解：

这题有很多做法

1. 搜索复杂度$O(n^4)$ 但是实际上远远达不到这个复杂度所以可以通过

2. 对于每一个格子，我们枚举每一行，找到每一行离他最近的格子

当前格子向右移动时，每一行离他最近的格子不可能向左移动，所以复杂度$O(n^3)$

3. dp 一共四个方向左上到右下左下到右上右上到左下右下到左上

然后分别dp 找到这个方向离他最近的格子以左上到右下为例 $f[i][j]$可由$f[i-1][j],f[i][j-1],f[i-1][j-1]$转移得到

复杂度$O(n^2)$

Code：

1. 搜索

 #include<cmath>

 #include<math.h>

 #include<ctype.h>

 #include<algorithm>

 #include<bitset>

 #include<cassert>

 #include<cctype>

 #include<cerrno>

 #include<cfloat>

 #include<ciso646>

 #include<climits>

 #include<clocale>

 #include<complex>

 #include<csetjmp>

 #include<csignal>

 #include<cstdarg>

 #include<cstddef>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<ctime>

 #include<cwchar>

 #include<cwctype>

 #include<deque>

 #include<exception>

 #include<fstream>

 #include<functional>

 #include<iomanip>

 #include<ios>

 #include<iosfwd>

 #include<iostream>

 #include<istream>

 #include<iterator>

 #include<limits>

 #include<list>

 #include<locale>

 #include<map>

 #include<memory>

 #include<new>

 #include<numeric>

 #include<ostream>

 #include<queue>

 #include<set>

 #include<sstream>

 #include<stack>

 #include<stdexcept>

 #include<streambuf>

 #include<string>

 #include<typeinfo>

 #include<utility>

 #include<valarray>

 #include<vector>

 #include<string.h>

 #include<stdlib.h>

 #include<stdio.h>

 using namespace std;

 int n;

 int a[][];

 const int dx[]={,,-,},dy[]={,,,-},cx[]={-,,,-},cy[]={-,-,,};

 int bfs(int x,int y,int k){

     if(a[x][y]) return a[x][y];

     if(k>=*n-) return ;

     int cnt=;

     int ok=;

     for(int d=;d<;d++){

         int nwx=x+k*dx[d],nwy=y+k*dy[d];

         for(int i=;i<=k;i++){

             if(nwx>= && nwx<=n && nwy>= && nwy<=n && a[nwx][nwy]){

                 if(ok==){

                     ok=a[nwx][nwy];

                 }

                 else{

                     cnt=;

                 }

             }

             nwx=nwx+cx[d];

             nwy=nwy+cy[d];

         }

     }

     if(cnt==) return ;

     else if(ok) return ok;

     else return bfs(x,y,k+);

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             scanf("%d",&a[i][j]);

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

         for(int j=;j<=n;j++)

             printf("%d ",bfs(i,j,));

         puts("");

     }

     return ;

 }

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<vector>

 #include<map>

 #include<set>

 #include<cmath>

 #include<iostream>

 #include<queue>

 #include<string>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef long double ld;

 typedef unsigned long long ull;

 typedef pair<long long,long long> pll;

 #define fi first

 #define se second

 #define pb push_back

 #define mp make_pair

 #define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)

 #define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)

 ll read(){

     ll x=,f=;char c=getchar();

     while(c<'' || c>''){if(c=='-')f=-;c=getchar();}

     while(c>='' && c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 const int maxn=;

 int n;

 int a[maxn][maxn];

 int col[maxn];

 int b[maxn][maxn],num[maxn];

 int main(){

 #ifdef LZT

     freopen("in","r",stdin);

 #endif

     n=read();

     rep(i,,n)

         rep(j,,n){

             a[i][j]=read();

             if(a[i][j]){

                 num[i]++;

                 b[i][num[i]]=j;

             }

         }

     rep(i,,n){

         rep(j,,n) col[j]=;

         rep(j,,n){

             if(a[i][j]==){

                 int mndis=1e9,mn=-;

                 rep(k,,n){

                     int nw=1e9,xx=-;

                     if(col[k]<=num[k] && nw>abs(b[k][col[k]]-j)+abs(k-i)){

                         nw=abs(b[k][col[k]]-j)+abs(k-i);

                         xx=a[k][b[k][col[k]]];

                     }

                     if(col[k]<num[k]){

                         int nwdis=abs(b[k][col[k]+]-j)+abs(k-i);

                         if(nw>nwdis){

                             nw=nwdis;

                             xx=a[k][b[k][col[k]+]];

                         }

                         else if(nw==nwdis){

                             xx=-;

                         }

                     }

                     if(mndis>nw){

                         mndis=nw;mn=xx;

                     }

                     else if(mndis==nw){

                         mn=-;

                     }

                     //cout<<i<<' '<<j<<' '<<k<<' '<<col[k]<<' '<<xx<<endl;

                 }

                 if(mn!=-) a[i][j]=mn;

             }

             rep(k,,n){

                 if(col[k]<num[k] && abs(b[k][col[k]]-(j+))>abs(b[k][col[k]+]-(j+))) col[k]++;

             }

         }

     }

     rep(i,,n){

         rep(j,,n)

             printf("%d ",a[i][j]);

         puts("");

     }

     return ;

 }

没写过

不过应该很好写

Review：

水题

数据也很水

比如第一个代码在所有格子均为0的时候复杂度是严格$O(n^4)$的但是竟然跑得比第二个代码快300ms。。。

每种做法都挺好想

巴特西

[NewTrain 10][poj 2329]Nearest Number - 2

题面：

题解：

Code：

Review：

最新文章

热门文章