深度搜索
POJ 1979
- POJ 1979题目链接
这个题目跟找池子差不多 ，而且这个题只要找片同色的瓦块的区域， 很明显的可以用深度搜索。
#include<iostream>
#include<string.h>
using namespace std;
char mat[1002][1002];
int m, n;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int ans;
void dfs(int x, int y){
mat[x][y] = '#';
for(int i = 0; i < 4; ++i){
int gx = x + dx[i], gy = y + dy[i];
if(0 <= gx && gx < m && 0 <= gy && gy < n
&& mat[gx][gy] == '.'){
ans++;
dfs(gx, gy);
}
}
return ;
}
int main(){
while(cin>>n>>m && m > 0 && n > 0){
memset(mat, 0, sizeof(mat));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin>>mat[i][j];
}
}
ans = 1;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(mat[i][j] == '@'){
dfs(i, j);
}
}
}
cout<<ans<<endl;
}
return 0;
}
AOJ0118
- AOJ 0118题目链接
这个题目就是把邻近相同的符号化为一块区域， 统计区域数目。
#include<iostream>
#include<string.h>
using namespace std;
char mat[1002][1002];
int m, n;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int ans;
int dfs(int x, int y, char ch){
mat[x][y] = '.';
for(int i = 0; i < 4; ++i){
int gx = x + dx[i], gy = y + dy[i];
if(0 <= gx && gx < m && 0 <= gy && gy < n
&& mat[gx][gy] == ch){
dfs(gx, gy, ch);
}
}
return 0;
}
void solve(){
memset(mat, 0, sizeof(mat));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin>>mat[i][j];
}
}
ans = 0;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(mat[i][j] != '.'){
ans++;
dfs(i, j, mat[i][j]);
}
}
}
cout<<ans<<endl;
}
int main(){
while(cin>>m>>n && m > 0 && n > 0){
solve();
}
return 0;
}
AOJ 0033
題意球掉在两个袋子里， 下来的球不能放在比他大的球上， 要求判断10个球能不能按要求下落。
基本思路就是左右比较， 为了突出深度搜索，写成了递归额形式。
#include<iostream>
#include<string.h>
using namespace std;
int a[12];
int n;
bool dfs(int i, int left, int right){
if(i == 10){
return true;
}
if(a[i] > left && dfs(i + 1, a[i], right)){
return true;
}
if(a[i] > right && dfs(i + 1, left, a[i])){
return true;
}
return false;
}
void solve(){
for(int i = 0; i < 10; ++i){
cin>>a[i];
}
if(dfs(0, 0, 0)){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
int main(){
cin>>n;
while(n--){
solve();
}
return 0;
}
AOJ 3009
- AOJ 3009 题目链接
扔石头，上下左右四个方向如果某一个方向紧挨着block就不能扔这个方向，否则碰到block停住，block消失，再次四个方向扔。DFS老一套，不过一定要注意判断紧挨着的情况。超过最小步数剪枝也是个很有意思的技巧。
#include<iostream>
#include<string.h>
const int VACANT_TYPE = 0;
const int BLOCK_TYPE = 1;
const int START_TYPE = 2;
const int GOAL_TYPE = 3;
const int MAX_THROW = 10;
using namespace std;
int mat[102][102];
int m, n;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int ans;
void dfs(int x, int y, int step){
if(step >= MAX_THROW){
return ;
}
for(int i = 0; i < 4; ++i){
int gx = x, gy = y;
while(true){
gx += dx[i], gy += dy[i];
if(gx < 0 || gx >= m || gy < 0 || gy >= n){
break;
}
if(mat[gx][gy] == GOAL_TYPE){
ans = min(ans, step + 1);
break;
}
if(mat[gx][gy] == BLOCK_TYPE){
mat[gx][gy] = VACANT_TYPE;
int prex = gx - dx[i], prey = gy - dy[i];
if(!(prex == x && prey == y)){
//剪枝
dfs(prex, prey, step + 1);
}
mat[gx][gy] = BLOCK_TYPE;
break;
}
}
}
return ;
}
void solve(){
ans = 10000;
memset(mat, -1, sizeof(mat));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin>>mat[i][j];
}
}
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(mat[i][j] == START_TYPE){
dfs(i, j, 0);
}
}
}
if(ans == 10000){
ans = -1;
}
cout<<ans<<endl;
}
int main(){
while(cin>>n>>m && n >0 && m > 0){
solve();
}
return 0;
}
广度搜索
AOJ 0558
输入m, n, N， 求 S->1, 1->2， 2->3, ..., 3->N的最短路径。
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
typedef pair<int, int>P;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int m, n, N;
char mat[1002][1002];
int d[1002][1002];
int ans;
int bfs(int sx, int sy, int goal){
memset(d, -1, sizeof(d));
queue<P>que;
que.push(P(sx, sy));
d[sx][sy] = 0;
while(que.size()){
P p = que.front();
que.pop();
int x = p.first, y = p.second;
if(mat[x][y] == goal){
return d[x][y];
}
for(int i = 0; i < 4; ++i){
int gx = x + dx[i], gy = y + dy[i];
if(0 <= gx && gx < m && 0 <= gy && gy < n
&& mat[gx][gy] != 'X' && d[gx][gy] == -1){
que.push(P(gx, gy));
d[gx][gy] = d[x][y] + 1;
}
}
}
}
void solve(){
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin>>mat[i][j];
}
}
ans = 0;
char start = 'S';
for(int k = 0; k < N; ++k){
char goal = '1' + k;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(mat[i][j] == start){
ans += bfs(i, j, goal);
}
}
}
start = goal;
}
cout<<ans<<endl;
}
int main(){
while(cin>>m>>n>>N && m > 0 && n > 0){
solve();
}
return 0;
}
AOJ 0121