Day7

Day7

今天学习的是dfs
常规操作~~~~没写完题
这次不是debug了,是真的不会(太菜了。。。)
未完待续

链接:https://vjudge.net/contest/313683#overview

Oil Deposits

Problem Description
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or@’, representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//板子题,8个方向
#include<bits/stdc++.h>
using namespace std;
const int mod = 101;
char a[mod][mod];
int vis[mod][mod];
int ans;
int n, m;
int d[8][2] = {
-1, 1,
-1, 0,
-1, -1,
0, 1,
0, -1,
1, 1,
1, 0,
1, -1
};

void DFS(int x, int y)
{
if(x < 0 || y < 0 || x >=n || y >= m)
return ;
int xx, yy;
// vis[x][y] = 1;
for(int i = 0; i < 8; i ++)
{
xx = x + d[i][0];
yy = y + d[i][1];
if(xx >= 0 && yy >= 0 && xx < n && yy < m && a[xx][yy] != '*')
{
a[xx][yy] = '*';
DFS(xx, yy);
}
}
}


int main()
{
int sx, sy;
while(~scanf("%d %d",&n, &m) && n)
{
// memset(vis, 0, sizeof(vis));
ans = 0;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
cin >> a[i][j];
}
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(a[i][j] == '@')
{

ans ++;
DFS(i, j);
}
}
}
cout << ans << endl;
}

return 0;
}

How Many Equations Can You Find

Problem Description
Now give you an string which only contains 0, 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9.You are asked to add the sign ‘+’ or ’-’ between the characters. Just like give you a string “12345”, you can work out a string “123+4-5”. Now give you an integer N, please tell me how many ways can you find to make the result of the string equal to N .You can only choose at most one sign between two adjacent characters.
Input
Each case contains a string s and a number N . You may be sure the length of the string will not exceed 12 and the absolute value of N will not exceed 999999999999.
Output
The output contains one line for each data set : the number of ways you can find to make the equation.

1
2
3
4
5
6
Sample Input
123456789 3
21 1
Sample Output
18
1

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//每一位都可能放或者不放算术符
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 200 + 10;
char str[MAXN][MAXN];
bool vis[MAXN][MAXN];
char s[100100];
ll n,m,len;
ll ans;
void DFS(int sum,int m){
if(m==len){
if(sum==n){
ans++;
}
return ;
}
ll mm=0;
for(int i=m;i<len;i++){
mm=mm*10+(s[i]-'0');
DFS(sum+mm,i+1);
if(m!=0){
DFS(sum-mm,i+1);
}
}
}
int main(){
while(scanf("%s%lld",s,&n)!=EOF){
ans=0;
len=strlen(s);
DFS(0,0);
printf("%d\n",ans);
}
return 0;
}

N皇后问题

Problem Description
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。

Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。

1
2
3
4
5
6
7
8
9
Sample Input
1
8
5
0
Sample Output
1
92
10

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
//第一种写法
#include<bits/stdc++.h>
using namespace std;
int vis[3][20], p[20]; // vis用来存储↖↑↗在此三个方向都不能有皇后 p[n]用来存储解
int n;
int num;

void DFS(int row)
{
int i;
if(row == n + 1) //已经够n行了
{
num ++;
return ;
}
for(i = 1; i <= n; i ++)
{
if(vis[0][row - i + n] == 0 && vis[1][i] == 0 && vis[2][row + i] == 0)
{
vis[0][row - i + n] = vis[1][i] = vis[2][row + i] = 1;//变值
DFS(row + 1);
vis[0][row - i + n] = vis[1][i] = vis[2][row + i] = 0;//回溯
}
}
}


int main()
{
for(n = 1; n <= 10; n ++) //打表防超时
{
memset(vis, 0, sizeof(vis));
num = 0;
DFS(1);
p[n] = num;
}
while(~scanf("%d",&n) && n)
{
cout << p[n] << endl;
}

return 0;
}

//第二种
#include<bits/stdc++.h>
using namespace std;

const int N = 12;
int a[N], cnt;
//x,i表示行,y,a[i]表示列,用check来表示是否可以放置
bool check(int x, int y)
{
for(int i = 1; i < x; i ++)
{
//abs(x - i) == abs(a[i] - y)表示的是(x-i)/(a[i]-y)的斜率的绝对值是否为1
if(a[i] == y || abs(x - i) == abs(a[i] - y))
return false;
}
return true;
}

void DFS(int x, int m)
{
//x越界的时候,同时也表示到底了,回溯
if(x > m)
{
cnt ++;
return ;
}
for(int i = 1; i <= m; i ++)
{
if(check(x, i))
{
a[x] = i;
DFS(x + 1, m);
}
}
return ;
}
int main()
{
//ans用来存放数据,不打表的话可能超时
int i, ans[11];
//打表并深搜
for(int i = 1; i < 11; i ++)
{
cnt = 0;
DFS(1, i);
ans[i] = cnt;
}
while(cin >> i)
{
if(i == 0) return 0;
cout << ans[i] << endl;
}
}
//第三种
//行,列,两个对角,共四个数组,每次存入都要查看是否已经存放过
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int a[105],b[105],c[105],d[105];//a:行,b:列,c:左下到右上,d:左上到右下
int i,ans=0;
void DFS(int x){
if(x==i+1){
ans++;
}
for(int j=1;j<=i;j++){
if(!b[j]&&!c[j+x]&&!d[x-j+i]){
a[x]=j;
b[j]=1;
c[j+x]=1;
d[x-j+i]=1;
DFS(x+1);
b[j]=0;
c[j+x]=0;
d[x-j+i]=0;
}
}
}
int main(){
int num[15];
int n;
for(i=1;i<11;i++)
{
ans=0;
DFS(1);
num[i]=ans;
}
while(cin>>n&&n)
{
cout<<num[n]<<endl;
}
return 0;
}

Fox And Two Dots

Problem Description
Fox Ciel is playing a mobile puzzle game called “Two Dots”. The basic levels are played on a board of size n × m cells, like this:

Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors.
The key of this game is to find a cycle that contain dots of same color. Consider 4 blue dots on the picture forming a circle as an example. Formally, we call a sequence of dots d1, d2, …, dk a cycle if and only if it meets the following condition:
These k dots are different: if i ≠ j then di is different from dj.
k is at least 4.
All dots belong to the same color.
For all 1 ≤ i ≤ k - 1: di and di + 1 are adjacent. Also, dk and d1 should also be adjacent. Cells x and y are called adjacent if they share an edge.
Determine if there exists a cycle on the field.
Input
The first line contains two integers n and m (2 ≤ n, m ≤ 50): the number of rows and columns of the board.
Then n lines follow, each line contains a string consisting of m characters, expressing colors of dots in each line. Each character is an uppercase Latin letter.
Output
Output “Yes” if there exists a cycle, and “No” otherwise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Examples
Input
3 4
AAAA
ABCA
AAAA
Output
Yes
Input
3 4
AAAA
ABCA
AADA
Output
No
Input
4 4
YYYR
BYBY
BBBY
BBBY
Output
Yes
Input
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
Output
Yes
Input
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
Output
No
Note
In first sample test all 'A' form a cycle.
In second sample there is no such cycle.
The third sample is displayed on the picture above ('Y' = Yellow, 'B' = Blue, 'R' = Red).

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//d
#include<iostream>
#include<cstring>
using namespace std;
int vis[55][55];
char a[55][55];
int d[4][2] = {
-1, 0,
1, 0,
0, 1,
0, -1
};
int n, m, k;
//四个变量表示当前坐标点和上一个坐标点
void DFS(int x, int y, int cx, int cy)
{

if(vis[x][y] == 1)
{
//想要表示成环,只需要走以前走过的点就行了,也就是走到了标记过的点
k = 1; //表示成环
return;
}
vis[x][y] = 1;
int xx, yy;
for(int i = 0; i < 4; i ++)
{
xx = x + d[i][0];
yy = y + d[i][1];
// 表示不能往回走并且不能越界
if(xx >= 0 && yy >= 0 && xx < n && yy < m && a[xx][yy] == a[x][y] && (xx != cx || yy != cy))
{
DFS(xx, yy , x, y);
}
}
}

int main()
{
while(~scanf("%d %d",&n, &m))
{
k = 0;
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; i ++)
{
scanf("%s",&a[i]);
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
//全部遍历,找寻可能点
if(vis[i][j] == 1) continue;
DFS(i, j, i, j);
//找到了点,退出循环
if(k == 1) break;
}
if(k == 1) break;
}
if(k == 1) puts("Yes");
else puts("No");

}
return 0;
}

棋盘问题

Problem Description
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
Output
对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

1
2
3
4
5
6
7
8
9
10
11
12
13
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN = 200 + 10;
char str[MAXN][MAXN];
bool vis[MAXN];
int n,k;
ll ans;
int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
void DFS(int x,int num){
if(num==k){
ans++;
return;
}
for(int i=x;i<n;i++){
for(int j=0;j<n;j++){
if(str[i][j]=='#'&&!vis[j]){
vis[j]=true;
DFS(i+1,num+1);
vis[j]=false;
}
}
}
}
main(){
while(scanf("%d%d",&n,&k)!=EOF&&n!=-1&&k!=-1){
memset(str,0,sizeof(str));
memset(vis,false,sizeof(vis));
ans=0;
for(int i=0;i<n;i++){
scanf("%s",str[i]);
}
DFS(0,0);
printf("%lld\n",ans);
}
return 0;
}

Sudoku

Problem Description
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.

Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//每个为0的格子都可能放1~9放完后再查看每一行,列,每个小九宫格中是否含有这个数,如果没有则继续DFS下个格子
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int a[10][10];
int check(int n,int num)
{
for(int i=0;i<9;i++)
{
int j=n%9;
if(a[i][j]==num)
return 0;
}
for(int j=0;j<9;j++)
{
int i=n/9;
if(a[i][j]==num)
return 0;
}
int ii=n/9/3*3;
int jj=n%9/3*3;
for(int i=ii;i<ii+3;i++)
for(int j=jj;j<jj+3;j++)
{
if(a[i][j]==num)
return 0;
}
return 1;
}
int temp;
int DFS(int n)
{
if(n>=81)
{
temp=1;
return 0;
}
if(a[n/9][n%9]!=0)
DFS(n+1);
else
{
for(int i=1;i<=9;i++)
{
if(check(n,i)==1)
{
a[n/9][n%9]=i;
DFS(n+1);
if(temp==1)
return 0;
a[n/9][n%9]=0;
}
}
}

}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
temp=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
scanf("%1d",&a[i][j]);
DFS(0);
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
printf("%d",a[i][j]);
printf("\n");
}
}
return 0;
}

放苹果

Problem Description
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
Input
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
Output
对输入的每组数据M和N,用一行输出相应的K。

1
2
3
4
5
Sample Input
1
7 3
Sample Output
8

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
//#include<>
using namespace std;
int n, m;

int solve(int m, int n)
{
if(m == 0 || n == 1) return 1;
if(n > m) return solve(m, m);
else
{
return solve(m, n - 1) + solve(m - n, n);
}
}

int main()
{
int t;
cin >> t;
while(t --)
{
cin >> m >> n;
int ans = solve(m, n);
cout << ans << endl;
}
return 0;
}
//PS:苹果可以为0, 盘子不能为0(毕竟是放苹果)
/*
分析:
如果盘子比苹果多,那么一定会有盘子是空的,即为 solve(m, m);
那么这就是一种情况
如果盘子比苹果少,那么可以分为:
1. 假设没有空盘子,那么上面都有苹果,那么可以看成一开始每个盘子上都有一个苹果
然后我们每次加一个苹果,就剩下m - n个苹果,直到放完为止
即为 solve(m - n, n)
2. 假设有空盘子,那么每次拿走一个空盘子 即为: solve(m, n - 1);

结果即为这两种情况的和
*/

Tempter of the Bone

Problem Description
小明做了一个很久很久的梦,醒来后他竟发现自己和朋友在一个摇摇欲坠的大棋盘上,他们必须得想尽一切办法逃离这里。
经过长时间的打探,小明发现,自己所在的棋盘格子上有个机关,上面写着“你只有一次机会,出发后t秒大门会为你敞开”,而他自己所在的棋盘是大小为 N*M 的长方形,他可以向上下左右四个方向移动(不可走有障碍点)。棋盘中有一扇门。根据机关的提示,小明顿时明白了,他和朋友必须在第 t 秒到门口。而这一切,没有回头路!因为一旦他移动了,他刚才所在的点就会消失,并且他不能在一个点上停留超过一秒,不然格子会爆炸。大逃亡开始了,请问小明和朋友能安全的逃出这奇怪的棋盘吗?
Input
输入多组测试数据。每个测试用例的第一行包含三个整数 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 ),分别表示棋盘的大小和门打开的时间。接下来的N行给出棋盘布局,每一行包含M个字符。其中
“.”: 无障碍点
“X”: 障碍点
“S”: 起点
“D”: 门
输入以 3 个 0 结束。这个测试用例不需要处理。
输入数据中的空格有些问题,请不要使用getchar(),如果一定要用可以选择scanf(“%s”,) 自动忽略空格
Output
对于每组样例输出一行。
如果小明能够安全逃出,输出 “YES” ,否则输出 “NO”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
int n, m, t;
char a[30][30];
int vis[40][40];

int d[4][2] = {
-1, 0,
1, 0,
0, 1,
0, -1
};
int flag;
int ex, ey;
void DFS(int sx, int sy, int ans)
{
int xx, yy;
//很重要,可以减少步骤,也是如何使一旦找到需要的路线就可以连续return出
if(flag)
return;
if(sx == ex && sy == ey && ans == t)
{
flag = 1;
return;
}
//剪枝的核心
int tem = t - ans - abs(ex - sx) - abs(ey - sy);
//剪枝:如果剩余的步数已经不足以走到出口,且必须是偶数,偶数-偶数=偶数,奇数-奇数=偶数,
if(tem < 0 || tem & 1)
return;
for(int i = 0; i < 4; i ++)
{
xx = sx + d[i][0];
yy = sy + d[i][1];
if(xx >= 0 && yy >= 0 && xx < n && yy < m && vis[xx][yy] == 0 && a[xx][yy] != 'X')
{
vis[xx][yy] = 1;
DFS(xx, yy, ans + 1);
if(flag)
return;
vis[xx][yy] = 0;
}
}
return;
}



int main()
{
int wall, sx, sy;
while(~scanf("%d %d %d",&n, &m, &t))
{
flag = 0, wall = 0;
if(n == 0 && m == 0 && t == 0) break;
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
cin >> a[i][j];
if(a[i][j] == 'S')
{
sx = i;
sy = j;
}
if(a[i][j] == 'D')
{
ex = i;
ey = j;
}
if(a[i][j] == 'X')
{
wall ++;
}
}
}
if(t > n * m - wall - 1)
{
puts("NO");
continue;
}
vis[sx][sy] = 1;
DFS(sx, sy, 0);
if(flag) puts("YES");
else puts("NO");
}

return 0;
}

/*
关于奇偶剪枝:
不利用奇偶剪枝的话一直TLE,现在对于奇偶剪枝不理解,暂时记住公式,t-cnt为目前剩余的时间,abs(x-dx)+abs(y-dy)为从当前改点到终点(门)所需要的最短步数,剩余时间为偶数(奇数),就需要走偶数步(奇数步),

奇数-偶数 = 奇数

而奇数-奇数= 偶数,偶数-偶数=偶数

所以只有当剩余的时间与目前位置到终点的最短步数奇偶性相同时,才有可能恰好在t时刻到大门的地方(因为中间会有墙,需根据题目条件继续判定,奇偶剪枝只是把范围缩小了)

还有就是开头时间步数可移动位置的数量关系,也属于剪枝 勿忘
abs(x-dx)+abs(y-dy)为从当前改点到终点(门)所需要的最短步数,但他会根据总时间的需要进行绕行,奇数步绕行后也是奇数步,偶数步绕行后也是偶数步,故他们之间奇偶性是相同的
2.此题一开始还有个纠结的问题,就是深搜如何搜到符合条件的路径后就直接退出,一开始不知道怎么解决,因为觉得深搜利用了递归,无法return一下,就直接结束,此时用一个ans来解决就OK了,当搜索多条路径时,记得要还原
需要在可能有变化找到结果标志flag及时return,
3.对于下一步要走的路径(1)先确定下一步要走哪个格 用for函数和方向数组(2)通过book标记数组和map地图数组判断这个位置
是否可以走(越界·是否是墙,是否已经测试或者走过)(3)标记这个位置已经走过(4)进入下一位置,传入这一数组(4)将以标记的数组撤回,以便下次再次搜索(6)将
改变的值再改回来
4.注意数组变量是否混合,每一个数组或者变量名是否改变
5,记得初始化,尤其是while函数
*/

Red and Black

Problem Description
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

‘.’ - a black tile
‘#’ - a red tile
‘@’ - a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
char a[30][30];
int vis[30][30];
int m, n;
int ans;
int d[4][2] = {
0, 1,
0, -1,
1, 0,
-1, 0
};
void DFS(int x, int y)
{
int xx, yy;
vis[x][y] = 1;

if(x < 0 || y < 0 || x >= n || y >= m)
return ;
for(int i = 0; i < 4; i ++)
{
xx = x + d[i][0];
yy = y + d[i][1];
if(xx >= 0 && yy >= 0 && xx < n && yy < m && vis[xx][yy] == 0 && a[xx][yy] != '#')
{
ans ++;
DFS(xx, yy);
}
}
}


int main()
{
int sx, sy;
while(~scanf("%d %d",&m, &n))
{
if(m == 0 && n == 0) break;
memset(vis, 0, sizeof(vis));
ans = 1;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
cin >> a[i][j];
if(a[i][j] == '@')
{
sx = i;
sy = j;
}
}
}
DFS(sx, sy);
cout << ans << endl;
}
return 0;
}

---------------- The End ----------------
0%