hdu 2589 dfs

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");}
}