hdu 2589 dfs"/>
hdu 2589 dfs
题意:中文题意画个图就明白了。这个题当时没做出,后来看别人代码理解做出的。
思路:用一个数组保存(1,1)到(i,j)的石头个数。然后dfs()遇到一个没有被染色的点,就开始枚举正方形,从小枚举到大,如果刚好那个点上就有一个石头,那就直接dfs(),否则就将正方形扩大,直到正方形里面有一个石头。
一直循环,到没有没被染色的区域。
代码注释的详细,具体见代码。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int dp[30][30];
int map[30][30];
int n,m;
int vis[30][30];
int dfs()
{ int x,y,flag=1;for(int i=1;i<=n&&flag;i++){for(int j=1;j<=n&&flag;j++)//找到一块空白区域{if(vis[i][j]==0){flag=0;x=i,y=j;}}}for(int k=0;k+x<=n&&k+y<=n&&!flag;k++)//将正方形的边长扩大 枚举,知道扩大到这个正方形里有两块石头就直接break,因为在继续扩大只会有更多的石头{int xx=k+x;int yy=k+y;int shi=dp[xx][yy]+dp[x-1][y-1]-dp[xx][y-1]-dp[x-1][yy];//求从空白区域到加上边长k的这个正方形里面的石头个数if(shi>1) break;if(shi==1){for(int i=x;i<=xx;i++){for(int j=y;j<=yy;j++){vis[i][j]=1;}}if(dfs()) return 1;for(int i=x;i<=xx;i++){for(int j=y;j<=yy;j++){vis[i][j]=0;}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(vis[i][j]==0) return 0;}}return 1;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);memset(map,0,sizeof(map));memset(dp,0,sizeof(dp));for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);map[x][y]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];//保寸1,1- i,j的石头个数}}memset(vis,0,sizeof(vis));if(dfs()) printf("YES\n");else printf("NO\n");}
}
更多推荐
hdu 2589 dfs
发布评论