poj 2870 Light Up 暴力搜索 + 剪枝

看了半天题目，原以为有什么高深的方法，没想到最后暴力加了个关键的剪枝就过了，，不过还是TLE了很多次。。。。。。

方法就是直接爆搜。。。。

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int mp[10][10];int n , m , lim;bool den[10][10];bool valid(int x,int y){return x>=1 && x<=n && y>=1 && y<=m;}bool check(){for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(mp[i][j] == -2)return false;if(mp[i][j]>=1 && mp[i][j] <= 4) return false;}}return true;}int dir[4][2] = {1,0,0,1,-1,0,0,-1};bool canput(int x,int y){for(int i = 0; i < 4; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(valid(tx,ty)){if( mp[tx][ty] == 0 ) return false;}}return true;}void go(int x,int y){if(mp[x][y]==-2){mp[x][y] = 5;return ;}if(mp[x][y]>=5)    mp[x][y]++;}void gao(int x,int y){for(int i = 0; i < 4; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(valid(tx,ty)){if(mp[tx][ty]>=1 && mp[tx][ty]<=4)mp[tx][ty] --;}}for(int i=y+1;i<=m;i++){go(x,i);if(mp[x][i]>=-1 && mp[x][i] <= 4) break;}for(int i=y-1;i>=1;i--){go(x,i);if(mp[x][i]>=-1 && mp[x][i] <= 4) break;}for(int i=x-1;i>=1;i--){go(i,y);if(mp[i][y]>=-1 && mp[i][y] <= 4) break;}for(int i=x+1;x<=n;i++){go(i,y);if(mp[i][y]>=-1 && mp[i][y] <= 4) break;}}void Go(int x,int y){if(mp[x][y]==5)    mp[x][y] = -2;if(mp[x][y]> 5)    mp[x][y] -- ;}void clear(int x,int y){for(int i = 0; i < 4; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(valid(tx,ty)){if(mp[tx][ty]>=0 && mp[tx][ty]<=3)mp[tx][ty] ++;}}for(int i=y+1;i<=m;i++){Go(x,i);if(mp[x][i]>=-1 && mp[x][i] <= 4) break;}for(int i=y-1;i>=1;i--){Go(x,i);if(mp[x][i]>=-1 && mp[x][i] <= 4) break;}for(int i=x-1;i>=1;i--){Go(i,y);if(mp[i][y]>=-1 && mp[i][y] <= 4) break;}for(int i=x+1;x<=n;i++){Go(i,y);if(mp[i][y]>=-1 && mp[i][y] <= 4) break;}}int ans;void dfs(int dep,int x,int y) {if(dep>ans) return ;if(x>n) {if(check()){if(dep<ans) ans=dep;}return ;}if(x>1 && mp[x-1][y]==-2 && mp[x][y]>=-1&&mp[x][y]<=4 ) return ;if(y<m) dfs(dep,x,y+1);else dfs(dep,x+1,1);if(mp[x][y]==-2){if(canput(x,y)) {den[x][y] = true;mp[x][y] = 5;gao(x,y);if(y<m) dfs(dep+1,x,y+1);else dfs(dep+1,x+1,1);den[x][y]=false;mp[x][y] = -2;clear(x,y);}}}int main(){int b , r , c , k ;while(scanf("%d%d",&n,&m),n||m){for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){mp[i][j] = - 2;}}scanf("%d",&b);for(int i = 0; i < b; i++){scanf("%d%d%d",&r,&c,&k);mp[r][c] = k;}ans = 1000;dfs(0,1,1);if(ans<1000)  printf("%d\n",ans);else puts("No solution");}return 0;}