[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. 搜索

 1 #include<cmath>
 2 #include<math.h>
 3 #include<ctype.h>
 4 #include<algorithm>
 5 #include<bitset>
 6 #include<cassert>
 7 #include<cctype>
 8 #include<cerrno>
 9 #include<cfloat>
10 #include<ciso646>
11 #include<climits>
12 #include<clocale>
13 #include<complex>
14 #include<csetjmp>
15 #include<csignal>
16 #include<cstdarg>
17 #include<cstddef>
18 #include<cstdio>
19 #include<cstdlib>
20 #include<cstring>
21 #include<ctime>
22 #include<cwchar>
23 #include<cwctype>
24 #include<deque>
25 #include<exception>
26 #include<fstream>
27 #include<functional>
28 #include<iomanip>
29 #include<ios>
30 #include<iosfwd>
31 #include<iostream>
32 #include<istream>
33 #include<iterator>
34 #include<limits>
35 #include<list>
36 #include<locale>
37 #include<map>
38 #include<memory>
39 #include<new>
40 #include<numeric>
41 #include<ostream>
42 #include<queue>
43 #include<set>
44 #include<sstream>
45 #include<stack>
46 #include<stdexcept>
47 #include<streambuf>
48 #include<string>
49 #include<typeinfo>
50 #include<utility>
51 #include<valarray>
52 #include<vector>
53 #include<string.h>
54 #include<stdlib.h>
55 #include<stdio.h>
56 using namespace std;
57 
58 int n;
59 int a[1010][1010];
60 const int dx[]={1,0,-1,0},dy[]={0,1,0,-1},cx[]={-1,1,1,-1},cy[]={-1,-1,1,1};
61 
62 int bfs(int x,int y,int k){
63     if(a[x][y]) return a[x][y];
64     if(k>=2*n-1) return 0;
65     int cnt=0;
66     int ok=0;
67     for(int d=0;d<4;d++){
68         int nwx=x+k*dx[d],nwy=y+k*dy[d];
69         for(int i=1;i<=k;i++){
70             if(nwx>=1 && nwx<=n && nwy>=1 && nwy<=n && a[nwx][nwy]){
71                 if(ok==0){
72                     ok=a[nwx][nwy];
73                 }
74                 else{
75                     cnt=1;
76                 }
77             }
78             nwx=nwx+cx[d];
79             nwy=nwy+cy[d];
80         }
81     }
82     if(cnt==1) return 0;
83     else if(ok) return ok;
84     else return bfs(x,y,k+1);
85 }
86 
87 int main(){
88     scanf("%d",&n);
89     for(int i=1;i<=n;i++)
90         for(int j=1;j<=n;j++)
91             scanf("%d",&a[i][j]);
92     for(int i=1;i<=n;i++){
93         for(int j=1;j<=n;j++)
94             printf("%d ",bfs(i,j,1));
95         puts("");
96     }
97     return 0;
98 }

View Code

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<map>
 7 #include<set>
 8 #include<cmath>
 9 #include<iostream>
10 #include<queue>
11 #include<string>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef long double ld;
16 typedef unsigned long long ull;
17 typedef pair<long long,long long> pll;
18 #define fi first
19 #define se second
20 #define pb push_back
21 #define mp make_pair
22 #define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
23 #define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
24 
25 ll read(){
26     ll x=0,f=1;char c=getchar();
27     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
28     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
29     return x*f;
30 }
31 
32 const int maxn=220;
33 int n;
34 int a[maxn][maxn];
35 int col[maxn];
36 int b[maxn][maxn],num[maxn];
37 
38 int main(){
39 #ifdef LZT
40     freopen("in","r",stdin);
41 #endif
42     n=read();
43     rep(i,1,n)
44         rep(j,1,n){
45             a[i][j]=read();
46             if(a[i][j]){
47                 num[i]++;
48                 b[i][num[i]]=j;
49             }
50         }
51     rep(i,1,n){
52         rep(j,1,n) col[j]=1;
53         rep(j,1,n){
54             if(a[i][j]==0){
55                 int mndis=1e9,mn=-1;
56                 rep(k,1,n){
57                     int nw=1e9,xx=-1;
58                     if(col[k]<=num[k] && nw>abs(b[k][col[k]]-j)+abs(k-i)){
59                         nw=abs(b[k][col[k]]-j)+abs(k-i);
60                         xx=a[k][b[k][col[k]]];
61                     }
62                     if(col[k]<num[k]){
63                         int nwdis=abs(b[k][col[k]+1]-j)+abs(k-i);
64                         if(nw>nwdis){
65                             nw=nwdis;
66                             xx=a[k][b[k][col[k]+1]];
67                         }
68                         else if(nw==nwdis){
69                             xx=-1;
70                         }
71                     }
72                     if(mndis>nw){
73                         mndis=nw;mn=xx;
74                     }
75                     else if(mndis==nw){
76                         mn=-1;
77                     }
78                     //cout<<i<<' '<<j<<' '<<k<<' '<<col[k]<<' '<<xx<<endl;
79                 }
80                 if(mn!=-1) a[i][j]=mn;
81             }
82             rep(k,1,n){
83                 if(col[k]<num[k] && abs(b[k][col[k]]-(j+1))>abs(b[k][col[k]+1]-(j+1))) col[k]++;
84             }
85         }
86     }
87 
88     rep(i,1,n){
89         rep(j,1,n)
90             printf("%d ",a[i][j]);
91         puts("");
92     }
93     return 0;
94 }

View Code

没写过

不过应该很好写

Review：

水题

数据也很水

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

每种做法都挺好想