当前位置: 代码迷 >> 综合 >> poj 1164 The Castle dp区域计数水题
  详细解决方案

poj 1164 The Castle dp区域计数水题

热度:51   发布时间:2024-01-19 06:01:46.0

水题,直接贴代码。

//poj 1164
//sep9
#include <iostream>
using namespace std;
int a[64][64];
int dp[64][64];
int n,m;
const int west=1,north=2,east=4,south=8;
void dfs(int x,int y)
{dp[x][y]=1;	if((a[x][y]&north)==0&&dp[x-1][y]==-1){dfs(x-1,y);dp[x][y]+=dp[x-1][y];}if((a[x][y]&south)==0&&dp[x+1][y]==-1){dfs(x+1,y);dp[x][y]+=dp[x+1][y];}if((a[x][y]&west)==0&&dp[x][y-1]==-1){dfs(x,y-1);dp[x][y]+=dp[x][y-1];	}if((a[x][y]&east)==0&&dp[x][y+1]==-1){dfs(x,y+1);dp[x][y]+=dp[x][y+1];}return ;
}int main()
{scanf("%d%d",&n,&m);int i,j;for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]); 	memset(dp,-1,sizeof(dp));int room_num=0,max_room=1;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(dp[i][j]==-1){++room_num;dfs(i,j);max_room=max(max_room,dp[i][j]);}printf("%d\n%d\n",room_num,max_room);return 0;
}