Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不知错哪里了?

Posted by 2009302574 at 2011-07-04 11:55:39 on Problem 1185
/**
*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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator