2份代码第3个点和第5个点轮流RE
by Pleasun @ 2018-07-06 14:50:08
我前面发的这个代码是第3个点RE,第一问为1的n=m=500
现在这个是第二份第5个点RE,第一问为0的n=m=500而且玄学的是我开O2就过了。。
```
#include <bits/stdc++.h>
using namespace std;
int n,m,mapx[550][550],s[550][550],ans=0,f=0,b[550],cnt,book[550][550];
struct node{
int x,y;
}a[550];
node p;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;
}
inline void bfs(node x);
bool cmp(node a,node b){
return a.x<b.x;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
mapx[i][j]=read();
}
}
for(int i=1;i<=m;i++){
memset(book,0,sizeof(book));
node t;
t.x=n;t.y=i;
bfs(t);
}
if(f!=0){
cout<<0<<endl<<f;
return 0;
}
for(int i=1;i<=m;i++){
if(b[i]==0)continue;
cnt++;
for(int j=1;j<=m+1;j++){
if(s[j][i]==0){
if(a[cnt].x==0)continue;
a[cnt].y=j-1;break;
}
if(a[cnt].x==0)a[cnt].x=j;
}
}
sort(a+1,a+1+cnt,cmp);
int p=1,maxsum=0,i=1;
while(p<m && i<=cnt){
maxsum=0;
while(a[i].x<=p+1){
if(i>cnt)break;
maxsum=max(a[i].y-p,maxsum);
i++;
}
ans++;
p+=maxsum;
}
cout<<1<<endl<<ans;
return 0;
}
inline void bfs(node x){
queue<node>q;
q.push(x);
book[x.x][x.y]=1;
node c;
bool f1=false;
while(!q.empty()){
p=q.front();
q.pop();
if(p.x<1 || p.x>n || p.y<1 || p.y>m)continue;
if(p.x==1)s[x.y][p.y]=1,f1=true,b[p.y]=1;
c.x=p.x-1;c.y=p.y;
if(mapx[p.x][p.y]<mapx[c.x][c.y] && book[c.x][c.y]==0){
book[c.x][c.y]=1;
q.push(c);
}
c.x=p.x;c.y=p.y-1;
if(mapx[p.x][p.y]<mapx[c.x][c.y] && book[c.x][c.y]==0){
book[c.x][c.y]=1;
q.push(c);
}
c.x=p.x;c.y=p.y+1;
if(mapx[p.x][p.y]<mapx[c.x][c.y] && book[c.x][c.y]==0){
book[c.x][c.y]=1;
q.push(c);
}
c.x=p.x+1;c.y=p.y;
if(mapx[p.x][p.y]<mapx[c.x][c.y] && book[c.x][c.y]==0){
book[c.x][c.y]=1;
q.push(c);
}
}
if(f1==false)f++;
}
```
by Pleasun @ 2018-07-06 14:55:57