题目：hdu4770:Lights Against Dudely

题目大意：同样是n*m的矩阵代表room，房间同样也有脆弱和坚固之分，现在要求要保护脆弱的房间，需要将每个脆弱的房间都照亮，但是坚固的房间不允许照到灯。灯是成L形的，即在x，y上有一盏灯，那么（x - 1， y）和（x， y + 1）就可以被照亮，当然包括（x，y）。题目又提供了一盏特殊的灯，它可以该改变方向，但是只有一盏，可以用也可以不用。一个房间最多一盏灯。问要将这些脆弱的房间都照亮最少需要多少盏灯。

解题思路：题目有说脆弱的房间最多15间，那么先枚举哪间脆弱的房间放特殊的灯，特殊的灯又需要枚举四个方向，之后的就都是普通的灯。复杂度（15 * 4 * 2^14）将近1000000，再加上只要碰到一个房间它不能被照亮就返回，并且这里考虑到普通灯的形状，所以回溯的时候是从左下角开始往右上角方向走，这是为了在比较前面得到较小的灯数目，那么回溯中有个剪枝就能剪掉较早的剪掉不符合的情况。剪枝：如果到中间的灯的数量比最小的大或是相等，就可以直接返回。

注意：这里灯的四个方向的坐标一定要细心，错在这找了一下午。还有中间不是有标记房间的状态：是否被照亮，这里回溯要改回原来的值这个地方也要小心。因为可能有的灯原先就是亮的。原先状态不一致。所以用tem数组做了记录。还有放在这个位置的灯若是照到了坚固的房间，或是已经放了灯的房间，这种情况是不行的。但是灯可以照在边界上，这种是可以的。感觉比较难的就是在回溯状态恢复这一块，一定要细心。

代码：

#include <stdio.h>
#include <string.h>

const int N = 205;
const int INF = 0x3f3f3f3f;
int n, m;
char g[N][N];
int visit[N][N]; //标记房间是否被照亮
int mm;
struct Tem {     //临时数组存放回溯后要恢复的状态

	int x, y, v;
};

const int dir[4][2][2] = {{{-1,0}, {0, 1}},  //特殊灯的四个方向
	{{1, 0}, {0, 1}}, 
	{{0, -1}, {1, 0}},
	{{0, -1}, {-1, 0}}};

int Min (const int x, const int y) { return x < y? x: y; }

bool influence (int x, int y, int d, Tem * tem) {  //d代表的是灯的方向  这个函数是用来处理这个位置的灯能影响到的房间，可以判断灯能不能放这个位置

	tem[0].v = visit[x][y];
	tem[0].x = x;
	tem[0].y = y;
	visit[x][y] = 1;
	int nx = x + dir[d][0][0];
	int ny = y + dir[d][0][1];
	if (nx >= 0 && nx < n && ny >= 0 && ny < m) {

		if (g[nx][ny] == '#')	
			return false;
		else {

			tem[1].v = visit[nx][ny];
			tem[1].x = nx;
			tem[1].y = ny;
			visit[nx][ny] = 1;
		}
	}

	int nx1 = x + dir[d][1][0];
	int ny1 = y + dir[d][1][1]; 
	if (nx1 >= 0 && nx1 < n && ny1 >= 0 && ny1 < m ) {

		if (g[nx1][ny1] == '#')	
			return false;
		else {

			tem[2].v = visit[nx1][ny1];
			tem[2].x = nx1;
			tem[2].y = ny1;
			visit[nx1][ny1] = 1;
		}
	}

	return true;
}

void undo (Tem * tem) {   //回溯恢复visit状态

	for (int i = 0; i < 3; i++)	
		if (tem[i].v != -1)
			visit[tem[i].x][tem[i].y] = tem[i].v;
}

void dfs (int x, int y, int num) {  //从左下角往右上角走

	int newx, newy;
	if (x == -1) {		

		mm = Min (mm, num);
		return;	
	}

	newy = y + 1; 
	newx = x;
	if (newy >= m) {
		newx = x - 1;
		newy = 0;
	}

	if (g[x][y] == '.') {         // 判断脆弱的房间是否要放灯

		bool flag = 0;
		if (visit[x][y]) {     //已经被照亮的房间可以考虑不放灯
			dfs(newx, newy, num);
			flag = 1;
		}

		if (num + 1 >= mm)    //剪枝  大于等于最小值直接返回
			return;

		Tem tem[3];           //放灯的情况
		memset (tem, -1, sizeof (tem));
		if (influence (x, y, 0, tem)) {

			g[x][y] = 'X';
			dfs (newx, newy, num + 1);
			undo(tem);
			g[x][y] = '.';

		} else {

			undo(tem);    //不论是否可以放都需要恢复状态，这个是因为我写的influence函数
			if (!flag)    //剪枝  这个房间不能被照亮直接返回
				return;
		}

	} else  	
		dfs (newx, newy, num);  
}

void solve () {   //枚举特殊灯的位置，特殊灯的方向

	mm = INF;
	memset (visit, 0, sizeof (visit));
	bool flag = 1;
	Tem tem[3];
	for (int i = 0; i < n; i++)  
		for (int j = 0; j < m; j++)
			if (g[i][j] == '.') {

				flag = 0;
				g[i][j] = 'X';
				for (int k = 0; k < 4; k++) {

					memset (tem, -1, sizeof (tem));
					memset (visit, 0, sizeof (visit));

					if (influence (i, j, k, tem))	
						dfs (n - 1, 0, 1);
					undo(tem);
				}
				g[i][j] = '.';
			}

	if (mm == INF) {

	        if (flag)
			printf ("0\n");
		else
			printf ("-1\n");
	}
	else
		printf ("%d\n", mm);
}

int main () {

	while (scanf ("%d%d", &n, &m), n || m) {

		for (int i = 0; i < n; i++) 
			scanf ("%s", g[i]);
		solve();	
	}
	return 0;
}

测试样例：

2 2
##
##
2 3 
#.. 
..#
3 3 
### 
#.# 
###  
4 2 
#. 
.. 
.# 
.. 
1 1 
. 
2 1 
. 
# 
1 2 
#. 
1 5 
.#... 
1 4 
.#.. 
2 5 
...#. 
####.  
6 4 
#.## 
..#. 
#.#. 
#..# 
.... 
....  
5 5 
#..#. 
##.#. 
####. 
#.### 
#..##  
2 2 
.. 
#. 
2 2 
.. 
.. 
2 2 
## 
.# 
2 2 
## 
#.  
2 3 
### 
#.. 
2 3 
#.# 
#.# 
0 0

输出：

0
2
-1
2
1
1
1
3
2
3
7
4
1
2
1
1
1
-1