poj 2870 Light Up(dfs+剪枝，写的稀烂)

半个下午+半个晚上，写的稀烂，各种粗心小错误，今天状态不佳啊。

一个点一个点枚举，判断是否可以放灯的时候就扫他的上下左右是否放过灯，用vis标记放过灯的位置。

放完全图后，再判断是否满足障碍物周围恰有那么多灯。

一个个点枚举过去会产生一个问题，回朔的时候状态太多，所以加一个剪枝：当前点右边，如果是障碍物，那障碍物上面（上面一整条，不是上面那个点）如果都没有灯，则剪掉。

我们是一个个点枚举过去，为什么会产生上面还是空的呢？就是因为加了回朔，

题目没有规定每一行都要有放灯，所以可以一整行一个灯都没有，所以就会出现上面的情况

写的太烂了，看看思路就好，我的代码就直接无视掉吧，900+ms擦边过，贴一下仅供批评。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define min(x,y) x<y?x:y
int map[10][10];
int tmap[10][10];
int vis[10][10];
int n,m,ans;
struct node
{
    int x,y,num;
};
vector<node> b;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int N;
bool inmap(int x,int y)
{
    return x>=0&&x<n&&y>=0&&y<m;
}
bool can(int r,int c)
{
    if(map[r][c]!=-4) return false;
    for(int d=0;d<4;d++)
    {
        int x=r,y=c;
        while(inmap(x+dx[d],y+dy[d]))
        {
            x+=dx[d];
            y+=dy[d];
            if(vis[x][y]) return false;
            if(map[x][y]>=-1) break;
        }
    }
    int nx=r+dx[3],ny=c+dy[3];
    if(inmap(nx,ny)&&map[nx][ny]>=-1&&nx>=1)
	{
		while(inmap(nx+dx[0],ny+dy[0]))
		{
			if(vis[nx+=dx[0]][ny+=dy[0]])
			{
				return true;
			}
		}
		return false;
	}
	return true;
}
void creat(int x,int y)
{
    tmap[x][y]=-2;
    for(int i=x-1;i>=0;i--)
        if(map[i][y]>=-1) break;
        else tmap[i][y]=-3;

    for(int i=x+1;i<n;i++)
        if(map[i][y]>=-1) break;
        else tmap[i][y]=-3;

    for(int i=y-1;i>=0;i--)
        if(map[x][i]>=-1) break;
        else tmap[x][i]=-3;

    for(int i=y+1;i<m;i++)
        if(map[x][i]>=-1) break;
        else tmap[x][i]=-3;
}
bool isok()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			tmap[i][j]=map[i][j];

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(vis[i][j]) creat(i,j);

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(tmap[i][j]==-4) return false;

    for(int i=0;i<b.size();i++)
    {
        int tot=0;
        for(int d=0;d<4;d++)
        {
            int nx=b[i].x+dx[d];
            int ny=b[i].y+dy[d];
            if(inmap(nx,ny)&&tmap[nx][ny]==-2)
            {
                tot++;
            }
        }
        if(tot!=b[i].num)
            return false;
    }
    return true;
}
void dfs(int v,int tot)
{
    if(tot>=ans) return;
    for(int i=v;i<N;i++)
    {
        int x=i/m;
        int y=i%m;
        if(can(x,y))
        {
            vis[x][y]=1;
            dfs(i+1,tot+1);
            vis[x][y]=0;
        }
    }
    if(isok())
    {
        ans=min(tot,ans);
    }
}
int main()
{
    int t,x,y,v;
    node a;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        N=n*m;
		b.clear();
        memset(map,-0x3f,sizeof(map));
		memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                map[i][j]=-4;
        scanf("%d",&t);
        for(int i=1;i<=t;i++)
        {
            scanf("%d%d%d",&x,&y,&v);
			x--;y--;
            map[x][y]=v;
            if(v!=-1)
            {
                a.x=x;a.y=y;a.num=v;
				b.push_back(a);
            }
        }
        ans=inf;
        dfs(0,0);
        if(ans!=inf)
        printf("%d\n",ans);
        else
        printf("No solution\n");
    }
    return 0;
}