P1535 [USACO08MAR] Cow Travelling S -搜索或dp
wflengxuenong · · 个人记录
题目大意：在一个迷宫上从
方法一，普通搜索
从终点出发，前起点方向走，如果能到起点就是一中方案。统计所有方案。得分
#include <bits/stdc++.h>
using namespace std;
int n, m, t, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[512][512];
void dfs(int x, int y, int tk) {
if(tk == 0) { if(x == r1[0] && y == r1[1]) cnt++; return; }
for(auto &fx : Fx)
{
int x_n = x + fx[0], y_n = y + fx[1];
if(x_n < 1 || y_n < 1 || x_n > n || y_n > m || grid[x_n][y_n])
continue;
dfs(x_n, y_n, tk-1);
}
}
int main() {
cin >> n >> m >> t;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
char tmp; cin >> tmp;
grid[i][j] = tmp == '*';
}
cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
dfs(r2[0], r2[1], t);
cout << cnt << endl;
return 0;
}方法二，考虑记忆化，步数总是从小到大的，如果前期已经处理过，直接拿来用即可。
设置记录步数的数组st，初始化为-1.设计起点的初值为1. 当一个点的四个方向处理完成后，这个点就没有必要再重复访问。 为什么初始设置为-1呢？这相当于访问标记。有的点路径数是0，如果初值为0，那么这些无效点可能会重复计算。
#include <bits/stdc++.h>
using namespace std;
int n, m, t, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[512][512];
int st[112][112][20];
int dfs(int x, int y, int tk) {
if(st[x][y][tk] !=-1)return st[x][y][tk];
if(tk == -1) { return 0; }
if(abs(r1[0]-x)+abs(r1[1]-y)>tk)return 0;//可行性剪枝。
int tmp=0;
for(auto &fx : Fx)
{
int x_n = x + fx[0], y_n = y + fx[1];
if(x_n < 1 || y_n < 1 || x_n > n || y_n > m || grid[x_n][y_n])
continue;
tmp+=dfs(x_n, y_n, tk-1);
}
return st[x][y][tk]=tmp;
}
int main() {
cin >> n >> m >> t;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
char tmp; cin >> tmp;
grid[i][j] = tmp == '*';
}
cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
memset(st,-1,sizeof(st));
st[r1[0]][r1[1]][0]=1;
dfs(r2[0], r2[1], t);
cout << st[r2[0]][r2[1]][t] << endl;
return 0;
}
方法4 DFS能写，bfs也一样可以写。
在处理入队的过程中，一个点可能从多个方向处理几次，但只需要入队一次，可以通过访问标记或者st的数值来标记入队情况，避免重复入队。
bfs总是中按照0，1，2这样的顺利来处理的。
#include <bits/stdc++.h>
using namespace std;
int n, m, k, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[112][112],vis[112][112][20];
int st[112][112][20];
struct node{
int x,y,st;
};
queue<node>q;
void bfs(){
q.push({r1[0],r1[1],0});
st[r1[0]][r1[1]][0]=1;
vis[r1[0]][r1[1]][0]=1;
while(q.size()){
node t=q.front();
q.pop();
if(t.st==k) continue;
for(int i=0;i<4;i++){
int tx=t.x+Fx[i][0],ty=t.y+Fx[i][1],ts=t.st+1;
if(tx>n||ty>m||tx<1||ty<1||grid[tx][ty])continue;
st[tx][ty][ts]+=st[t.x][t.y][t.st];
if(!vis[tx][ty][ts])q.push({tx,ty,ts}),vis[tx][ty][ts]=1;
}
}
}
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
char tmp; cin >> tmp;
grid[i][j] = tmp == '*';
}
cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
bfs();
cout << st[r2[0]][r2[1]][k] << endl;
return 0;
}方法四 动态规划
能用记忆化搜索来完成的题目基本可以动态规划。动态规划的特点是无后效性，本题只要通过步数来划分阶段，虽然结点间相互可达，但也有了先后关系。
设计状态为
//DP写法
#include <bits/stdc++.h>
using namespace std;
int n, m, t, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[512][512];
int st[112][112][20];
int main() {
cin >> n >> m >> t;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
char tmp;
cin >> tmp;
grid[i][j] = tmp == '*';
}
cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
// memset(st,-1,sizeof(st));
st[r1[0]][r1[1]][0]=1;
for(int l=1; l<=t; l++)
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
for(auto &fx : Fx) {
int x_n = i + fx[0], y_n = j + fx[1];
if(x_n < 1 || y_n < 1 || x_n > n || y_n > m || grid[x_n][y_n]||!st[x_n][y_n][l-1])
continue;
st[i][j][l]+=st[x_n][y_n][l-1];
}
}
cout << st[r2[0]][r2[1]][t] << endl;
return 0;
}
/*
10 10 7
**........
..**......
*.........
.*.*....*.
..........
..*.**....
..........
.**..*....
......**..
...***....
5 4 7 3
*/