|
|
back to boardwhat's there in the 18-th test? Posted by DEAL 5 Apr 2012 20:54 here is my program, but it doesn't work there, what can be the problem #include <iostream> #include <vector> using namespace std; #define Max 205 char now[Max]; int nn[Max][Max]; int pp[Max]; char no[20]="Just a picture"; char yes[20]="Island world"; int c=1; int list[Max*Max][5]; int add(int a, int b) { if(list[a][3]<=2) { list[a][list[a][3]]=b; list[a][3]++; } else { cout<<no; return -1; } if(list[b][3]<=2) { list[b][list[b][3]]=a; list[b][3]++; } else { cout<<no; return -1; } return 1; } int used[Max]; int timer=1; int tin[Max]; int tup[Max]; int exist=0; void dfs(int v, int p) { used[v]=1; tup[v]=tin[v]=timer; timer++; for(int i=0; i<3; i++) { int to=list[v][i]; if(to==p) continue; if(used[to]==1) tup[v]=min(tup[v],tin[to]); else { dfs(to,v); tup[v]=min(tup[v],tup[to]); if(tin[v]<tup[to]) { exist=1; } } } } int main() { /* freopen("INPUT.txt","r",stdin); freopen("OUTPUT.txt","w",stdout);*/ int w,h; cin>>w>>h; if(w%2==0 || h%2==0) { cout<<no; return 0; } memset(list,0,Max*Max*sizeof(list[0][0])); memset(nn,0,Max*Max*sizeof(nn[0][0])); memset(used,0,Max*sizeof(used[0])); cin.getline(now,w); for(int i=0; i<h; i++) { cin.getline(now,w+1); if(now[w-1]<=0) { cout<<no; return 0; } for(int j=0; j<w; j++) { if(now[j]=='O') { nn[i][j]=c; c++; } if(now[j]=='\\') nn[i][j]=-1; if(now[j]=='/') nn[i][j]=-2; if(now[j]=='|') nn[i][j]=-3; if(now[j]=='-') nn[i][j]=-4; if(now[j]==' ') nn[i][j]=-5; if(nn[i][j]==0) { cout<<no; return 0; } } } for(int i=0; i<h; i++) { for(int j=0; j<w; j++) { switch (nn[i][j]) { case -1: if(i==0 || i==h-1 || j==0 || j==w-1) { cout<<no; return 0; } if(nn[i-1][j-1]>0 && nn[i+1][j+1]>0) { if(add(nn[i-1][j-1],nn[i+1][j+1])==-1) return 0; } break; case -2: if(i==0 || i==h-1 || j==0 || j==w-1) { cout<<no; return 0; } if(nn[i+1][j-1]>0 && nn[i-1][j+1]>0) { if(add(nn[i+1][j-1],nn[i-1][j+1])==-1) return 0; } break; case -3: if(i==0 || i==h-1 ) { cout<<no; return 0; } if(nn[i-1][j]>0 && nn[i+1][j]>0) { if(add(nn[i-1][j],nn[i+1][j])==-1) return 0; } break; case -4: if(j==0 || j==w-1) { cout<<no; return 0; } if(nn[i][j-1]>0 && nn[i][j+1]>0) { if(add(nn[i][j-1],nn[i][j+1])==-1) return 0; } break; }
} } for(int i=1; i<c; i++) { if(list[i][3]!=3) { cout<<no; return 0; } } dfs(1,-1); if(exist==1) { cout<<no; return 0; } for(int i=1; i<c; i++) { if(used[i]==0) { cout<<no; return 0; } } cout<<yes; } |
|
|