算法笔记#4:深搜（DFS）

counting sheep

描述

A while ago I had trouble sleeping. I used to lie awake, staring at the ceiling, for hours and hours. Then one day my grandmother suggested I tried counting sheep after I'd gone to bed. As always when my grandmother suggests things, I decided to try it out. The only problem was, there were no sheep around to be counted when I went to bed.

Creative as I am, that wasn't going to stop me. I sat down and wrote a computer program that made a grid of characters, where # represents a sheep, while . is grass (or whatever you like, just not sheep). To make the counting a little more interesting, I also decided I wanted to count flocks of sheep instead of single sheep. Two sheep are in the same flock if they share a common side (up, down, right or left). Also, if sheep A is in the same flock as sheep B, and sheep B is in the same flock as sheep C, then sheeps A and C are in the same flock.


Now, I've got a new problem. Though counting these sheep actually helps me fall asleep, I find that it is extremely boring. To solve this, I've decided I need another computer program that does the counting for me. Then I'll be able to just start both these programs before I go to bed, and I'll sleep tight until the morning without any disturbances. I need you to write this program for me.

输入

The first line of input contains a single number T, the number of test cases to follow.

Each test case begins with a line containing two numbers, H and W, the height and width of the sheep grid. Then follows H lines, each containing W characters (either # or .), describing that part of the grid.

输出

For each test case, output a line containing a single number, the amount of sheep flock son that grid according to the rules stated in the problem description.

Notes and Constraints
0 < T <= 100
0 < H,W <= 100

样例输入

2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###

样例输出

6

3

"#"代表sheep，“.”代表grass，题目意思就是说如果羊是成群的，互相紧贴的，算一只，单个的羊也算一只。按照第一个例子来说，那五个挨在一起的羊就算作一只，再加上五个落单的，因此一共有6只。过程和上面的差不多。

#include 
using namespace std;
int  sum, n, m, dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1},i,j,k;
char map[110][110];
void dfs(int x, int y)
{
int d;	
map[x][y] = '.';for(d = 0; d < 4; d++){int nx=x+dx[d], ny=y+dy[d];if(nx>=0&&nx=0&&ny

#include
using namespace std;
int place[8]={0};//皇后摆放后所在的列
bool flag[8]={1,1,1,1,1,1,1,1};//标记占领，表示第col列是否可占用，1表示可
bool d1[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
bool d2[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};//初始化棋盘，全部都是1（可放），接下来0代表不可放。bool类型可以直接true or fluse
int number = 0;
void print();
void judge(int n);int main()
{judge(0);return 0;
}
void judge(int n)
{int c;for(c=0;c<8;c++){if(flag[c]&&d1[n-c+7]&&d2[n+c]){place[n]=c;//摆放皇后flag[c]=false;//宣布占领第col列d1[n-c+7]=false;//占领上对角线d2[n+c]=false;//占领下对角线if(n<7)//递归的出口就在这里，在第八行及第八行之前如果找到了可以放的地方就退出，执行打印judge(n+1);else print();//接下来开始回溯（探求所有可能的解）flag[c]=true;//删除皇后，将所有数据初始化，再次从头开始d1[n-c+7]=true;d2[n+c]=true;}}
}
void print()
{int col,i,j;number++;printf("No. %d\n",number);int table[8][8]={0};for(i=0;i<8;i++)table[i][place[i]]=1;for(j=0;j<8;j++)//注意，按照列优先的顺序输出。如果是行优先，for循环的位置换一换就行{for(i=0;i<8;i++){if(i==7)printf("%d",table[i][j]);elseprintf("%d ",table[i][j]);}printf("\n");}}//这题提交了很多次，都错在最后一个数后面多了一个空格，要用if语句判断下标不能漏

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！