### Oil Deposits

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.

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0


Sample Output

0
1
2
2

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
char s[105][105];
int vis[105][105];
int m,n,ans;
int d[8][2]={1,0,0,1,0,-1,-1,0,1,1,1,-1,-1,-1,-1,1};
void dfs(int x,int y)
{
vis[x][y]=1;
if(x<0||x>=m||y<0||y>=n)    return ;
for(int i=0;i<8;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=0&&dx<m&&dy>=0&&dy<n&&!vis[dx][dy]&&s[dx][dy]=='@')
{
s[dx][dy]='*';
dfs(dx,dy);
}
}
}
int main()
{
while(cin>>m>>n&&m)
{
memset(vis,0,sizeof(vis));
ans=0;
for(int i=0;i<m;i++)    cin>>s[i];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(s[i][j]=='@')
{
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
}
}


### How Many Equations Can You Find

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.

Sample Input

123456789 3
21 1

Sample Output

18
1

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
string s;int n,ans;
void dfs(int x,int now)//x代表的是当前要进行操作的位置，now代表当前得到的值
{
if(x==s.size())//如果x已经跟字符串的长度相等说明这一次遍历已经结束了
{
if(now==n)    ans++;//如果得到的值跟n相等，答案就加一
//        cout<<now<<endl;
return ;
}
for(int i=x;i<s.size();i++)
{
int mid=0;
for(int j=x;j<=i;j++)
{
mid=mid*10+s[j]-'0';//得到运算符左边字符串所代表数的大小
//            cout<<mid<<"?"<<now<<endl;
}
dfs(i+1,now+mid);//去访问下一个位置，并且此时的值加上上面得到的运算符左边字符串所代表的数
if(x)    dfs(i+1,now-mid);//减号不能放在最前面，所以要有一个x不为0的判断
}
}
int main()
{
while(cin>>s>>n)
{
ans=0;
dfs(0,0);//从s[0]开始，当前值为0
cout<<ans<<endl;
}
}


### N皇后问题

Description：

Input

Output

Sample Input

1
8
5
0

Sample Output

1
92
10

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int n,mid;
int ans[12],mmp[12];
void dfs(int x)
{
if(x==n+1)
{
mid++;
return ;
}
for(int i=1;i<=n;i++)
{
int flag=1;
mmp[x]=i;
for(int j=1;j<x;j++)
{
if(mmp[j]==i||(abs(j-x)==abs(mmp[j]-mmp[x])))
{
flag=0;
break;
}
}
if(flag)    dfs(x+1);
}
}
int main()
{
for(n=1;n<=10;n++)
{
mid=0;
dfs(1);
ans[n]=mid;
}
int t;
while(cin>>t&&t)
{
cout<<ans[t]<<endl;
}
}


### Fox And Two Dots

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:

1. These k dots are different: if i ≠ j then di is different from dj.
2. k is at least 4.
3. All dots belong to the same color.
4. 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.

Examples
Input

3 4
AAAA
ABCA
AAAA

Output

Yes

Input

3 4
AAAA
ABCA

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).
Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
char s[60][60];
int vis[60][60],flag,n,m,sx,sy;
int d[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int x,int y,int step)
{
if(flag)    return ;
vis[x][y]=1;
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx==sx&&dy==sy&&step>=4)
{
flag=1;
return ;
}
if(dx>=0&&dx<n&&dy>=0&&dy<m&&!vis[dx][dy]&&s[dx][dy]==s[x][y])
{
dfs(dx,dy,step+1);
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)    cin>>s[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
memset(vis,0,sizeof(vis));
sx=i,sy=j;
dfs(sx,sy,1);
}
}
if(flag)    puts("Yes");
else    puts("No");
}


### 棋盘问题

Description：

Input

Output

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1


Sample Output

2
1

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,vis[10],ans,now;
char s[10][10];
void dfs(int x)
{
if(now==k)
{
ans++;
return ;
}
if(x>=n)    return ;
for(int j=0;j<n;j++)
{
if(!vis[j]&&s[x][j]=='#')
{
vis[j]=1;
now++;
dfs(x+1);
now--;
vis[j]=0;
}
}
dfs(x+1);
}
int main()
{
while(scanf("%d %d",&n,&k)&&n!=-1&&k!=-1)
{
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)    cin>>s[i];
ans=0,now=0;
dfs(0);
cout<<ans<<endl;
}
}


### Sudoku

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.

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

Problem solving:

1. 如何用n来表示当前的位置
2. 如何判断同一行同一列以及同一小方格的同一行同一列有没有与之相同的数

n/9代表的就是当前位置的行，n%9代表的就是当前位置的列。
n/9/3*3表示的就是当前位置在小方格里的行，n%9/3*3代表的就是当前位置在小方格里的列。

Code:

#include<iostream>
#include<cstdio>
using namespace std;
int a[10][10],flag;
bool check(int n,int now)
{
for(int i=0;i<9;i++)
{
int j=n%9;
if(a[i][j]==now)
return 0;
}
for(int j=0;j<9;j++)
{
int i=n/9;
if(a[i][j]==now)
return 0;
}
int di=n/9/3*3;
int dj=n%9/3*3;
for(int i =di;i<di+3;i++)
{
for(int j=dj;j<dj+3;j++)
{
if(a[i][j]==now)    return 0;
}
}
return 1;
}
int dfs(int n)
{
if(n>=81)
{
flag=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(flag==1)
return 0;
a[n/9][n%9]=0;//回溯
}
}
}
//    cout<<"?"<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
flag=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]);
puts("");
}
}
return 0;
}


### 放苹果

Description：

Input

Output

Sample Input

1
7 3

Sample Output

8

Problem solving:

1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).

Code:

#include<iostream>
using namespace std;
int t,n,m,ans;
int dfs(int x,int y)
{
if(x==0||y==1){
return 1;
}
else if(x<y)    return dfs(x,x);
return dfs(x,y-1)+dfs(x-y,y);
}
int main()
{
cin>>t;
while(t--)
{
cin>>m>>n;
cout<<dfs(m,n)<<endl;
}
}


### Tempter of the Bone

Description：

Input

“.”: 无障碍点
“X”: 障碍点
“S”: 起点
“D”: 门

Output

Sample Input

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0


Sample Output

NO
YES

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,ex,ey,ti,flag;
char s[10][10];
int vis[10][10];
int d[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y)
{
if(x<0||x>=n||y<0||y>=m||ti>t)    return ;
if(flag)    return ;
if(s[x][y]=='D'&&ti==t)
{
//        cout<<ti<<endl;
flag=1;
return ;
}

int temp1 = abs(ex-x) + abs(ey-y);
int temp2 = abs(t-ti);
int temp = abs(temp1-temp2);
if(temp%2!=0)    return ;

vis[x][y]=1;
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=0&&dx<n&&dy>=0&&dy<m&&!vis[dx][dy]&&s[dx][dy]!='X')
{
//            cout<<ti<<"-->"<<dx<<" -->"<<dy<<"\n";
ti++;
dfs(dx,dy);
vis[dx][dy]=0;
ti--;
}
}
}
int main()
{
ios::sync_with_stdio(0);
while(cin>>n>>m>>t)
{
if(n==0&&m==0&&t==0)    break;
flag=0,ti=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)    cin>>s[i];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(s[i][j]=='S')
{
sx=i,sy=j;
}
else if(s[i][j]=='D')
{
ex=i,ey=j;
}
dfs(sx,sy);
if(flag)    puts("YES");
else    puts("NO");
}
}


### Red and Black

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).

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0


Sample Output

45
59
6
13

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
char s[25][25];
int vis[25][25];
int a,b,ans;
int d[4][2]={1,0,0,1,0,-1,-1,0};
void dfs(int x,int y)
{
vis[x][y]=1;
if(x<0||x>=b||y<0||y>=a)    return ;
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=0&&dx<b&&dy>=0&&dy<a&&!vis[dx][dy]&&s[dx][dy]!='#')
{
ans++;
dfs(dx,dy);
}
}
}
int main()
{
while(cin>>a>>b)
{
if(a==0&&b==0)    break;
ans=1;
memset(vis,0,sizeof(vis));
for(int i=0;i<b;i++)
{
for(int j=0;j<a;j++)
{
cin>>s[i][j];
}
}
for(int i=0;i<b;i++)
for(int j=0;j<a;j++)
{
if(s[i][j]=='@')    dfs(i,j);
}
cout<<ans<<endl;
}
}