Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
不知错哪里了?/** *1185--dfs */ #include <stdio.h> #include <string.h> int n,m,sum,max=0; char a[101][11]; int visited[101][11]={0};//visited[][]==-1 放炮,visited[][]>0 射程内 int canplace(int row,int col) { int r=row,c=col; //up r=row-1; if(r>=0&&visited[r][c]) return 0; r--; if(r>=0&&visited[r][c]) return 0; //down r=row+1; if(r<n&&visited[r][c]) return 0; r++; if(r<n&&visited[r][c]) return 0; //left r=row; c=col-1; if(c>=0&&visited[r][c]) return 0; c--; if(c>=0&&visited[r][c]) return 0; //right c=col+1; if(c<m&&visited[r][c]) return 0; c++; if(c<m&&visited[r][c]) return 0; // return 1; }//canplace void place(int row,int col) { int r=row,c=col; visited[r][c]=-1; //up r=row-1; if(r>=0) ++visited[r][c]; r--; if(r>=0) ++visited[r][c]; //down r=row+1; if(r<n) ++visited[r][c]; r++; if(r<n) ++visited[r][c]; //left r=row; c=col-1; if(c>=0) ++visited[r][c]; c--; if(c>=0) ++visited[r][c]; //right c=col+1; if(c<n) ++visited[r][c]; c++; if(c<n) ++visited[r][c]; }//place void takeout(int row,int col) { int r=row,c=col; visited[r][c]=0; //up r=row-1; if(r>=0) --visited[r][c]; r--; if(r>=0) --visited[r][c]; //down r=row+1; if(r<n) --visited[r][c]; r++; if(r<n) --visited[r][c]; //left r=row; c=col-1; if(c>=0) --visited[r][c]; c--; if(c>=0) --visited[r][c]; //right c=col+1; if(c<n) --visited[r][c]; c++; if(c<n) --visited[r][c]; }//takeout void dfs(int t) { int r=t/m,c=r%m; if(t>=n*m) max = sum>max?sum:max; else{ if(r>=0&&r<n&&c>=0&&c<m&&a[r][c]=='P'&&visited[r][c]==0&&canplace(r,c)) { place(r,c); sum++; dfs(t+1); sum--; takeout(r,c); } } } int main() { int i; scanf("%d%d",&n,&m); getchar(); for(i=0;i<n;i++) gets(a[i]); dfs(0); printf("%d\n",max); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator