| ||||||||||
| 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