2 条题解
-
2
P1902 刺杀大使
dfs!
超级简单的搜索
初始化
int n, m;//输入的行列 int p[1005][1005];//输入的地图 int f[9][5] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//方向 bool can[1005][1005];//判断走没走过 int b[105][105][1005];//记忆化 int ans = 100000000;//最小路径中的最大值输入
cin >> n >> m;//输入行和列 for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> p[i][j];//双重循环输入地图 } }dfs
调用dfs
dfs(1, 1, 0);//调用dfs，从1,1这个点作为起点，当前受伤为0dfs主函数
void dfs(int x, int y, int num) { if(b[x][y][num]) {//记忆化，当b[x][y][num]被记忆过了，那么直接return return ;//回溯 } b[x][y][num] = 1;//如果没有被记忆，那么记忆 int xx, yy;//定义xx和yy if(x == n) {//如果到了最后一行 ans = min(ans, num);//比较最小路径中的最大值和当前受到的伤害 return ;//回溯 } for(int i = 0; i < 4; i++) {//四个方向 xx = x + f[i][0];//x的移动 yy = y + f[i][1];//y的移动 if(check(xx, yy) && can[xx][yy] != 1) {//如果没有越界而且没被标记 can[xx][yy] = 1;//标记 dfs(xx, yy, max(num, p[xx][yy]));//继续走下一个点 can[xx][yy] = 0;//若回溯，则标记为没走 } } }check函数
int check(int x, int y) {//判断x和y有没有越界 if(x <= 0 || y <= 0 || x > n || y > m) { return 0;//越界返回0 } return 1;//没越界返回1 }输出
cout << ans << endl;//输出最小路径中的最大值完整代码
//头文件 #include <iostream> using namespace std; //初始化 int n, m; int p[1005][1005]; int f[9][5] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; bool can[1005][1005]; int b[105][105][1005]; int ans = 100000000; //check函数 int check(int x, int y) { if(x <= 0 || y <= 0 || x > n || y > m) { return 0; } return 1; } //dfs函数 void dfs(int x, int y, int num) { if(b[x][y][num]) { return ; } b[x][y][num] = 1; int xx, yy; if(x == n) { ans = min(ans, num); return ; } for(int i = 0; i < 4; i++) { xx = x + f[i][0]; yy = y + f[i][1]; if(check(xx, yy) && can[xx][yy] != 1) { can[xx][yy] = 1; dfs(xx, yy, max(num, p[xx][yy])); can[xx][yy] = 0; } } } //主函数 int main() { //输入 cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> p[i][j]; } } //调用dfs dfs(1, 1, 0); //输出 cout << ans << endl; //好习惯 return 0; }样例过了，直接提交**！**
50分！
多亏了记忆化，不然其实是0分~，别问我是怎么知道的~
dp
好吧，dp不行
啊？
为什么dp不行呢？
其实这个原理很简单，dp是借助前面已有的点更新接下来的点，而后面有可能来的点则不会更新，而正好这道题后面来的点有可能能更新前面的点
0 114 1 114 114 1 1 1 1 514 0 例如这个输入，最小的路径应该全是1**，但是显然dp无法做到**
dfs+二分！
我们需要增加哪些变量呢？
初始化
int n, m; bool flag;//一个bool，判断是否到了终点 int p[1005][1005]; int f[9][5] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; bool can[1005][1005]; int b[105][105][1005]; int l, r, mid;//二分三件套输入
cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> p[i][j]; l = min(l, p[i][j]);//二分左端点是输入中最小的数 r = max(r, p[i][j]);//二分右端点是输入中最大的数 } }二分+dfs
二分
while(l <= r) {//通过while二分 mid = (l + r) / 2;//mid取中间值 flag = 0;//每次将flag设置为没到终点 memset(can, 0, sizeof(can));//将标记数组清零 dfs(1, 1, mid);//调用dfs，1,1起点，搜索最多到mid if(flag == 0) {//如果没搜到，那么就是小了 l = mid + 1;//二分，将l调大 } else {//搜到了，有可能大了 r = mid - 1;//二分，将r调小 } }dfs
void dfs(int x, int y, int num) { int xx, yy; if(x == n) { flag = 1;//这里需要将flag设置为找到终点了 return ; } for(int i = 0; i < 4; i++) { xx = x + f[i][0]; yy = y + f[i][1]; if(check(xx, yy) && can[xx][yy] != 1 && p[xx][yy] < num) {//注意不能搜到大于等于num的点 can[xx][yy] = 1; dfs(xx, yy, num); //这里不用把标记数组设置为0了，因为回溯了就代表之后也走不了了 if(flag == 1) {//如果搜到了 return ;//可以直接回溯优化时间 } } } }check
//和上一个代码没有任何区别 int check(int x, int y) { if(x <= 0 || y <= 0 || x > n || y > m) { return 0; } return 1; }完整代码
//头文件 #include <iostream> #include <string.h> using namespace std; //初始化 int n, m; bool flag; int p[1005][1005]; int f[9][5] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; bool can[1005][1005]; int b[105][105][1005]; int l, r, mid; //check函数 int check(int x, int y) { if(x <= 0 || y <= 0 || x > n || y > m) { return 0; } return 1; } //dfs函数 void dfs(int x, int y, int num) { int xx, yy; if(x == n) { flag = 1; return ; } for(int i = 0; i < 4; i++) { xx = x + f[i][0]; yy = y + f[i][1]; if(check(xx, yy) && can[xx][yy] != 1 && p[xx][yy] < num) { can[xx][yy] = 1; dfs(xx, yy, num); if(flag == 1) { return ; } } } } //主函数 int main() { //输入 cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> p[i][j]; l = min(l, p[i][j]); r = max(r, p[i][j]); } } //二分 while(l <= r) { mid = (l + r) / 2; flag = 0; memset(can, 0, sizeof(can)); dfs(1, 1, mid); if(flag == 0) { l = mid + 1; } else { r = mid - 1; } } //输出 cout << r << endl;//输出r或者l-1都行，因为二分先判断哪个就输出哪个 return 0;//好习惯~ }提交!
AC!
-
1
#include<bits/stdc++.h> using namespace std; int get() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); } while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x * f; } const int MaxN = 1005; const int inf = 0x3f3f3f3f; const int dx[5] = {0, 1, 0, -1, 0}; const int dy[5] = {0, 0, 1, 0, -1}; int p[MaxN][MaxN], vis[MaxN][MaxN]; int n, m; int l = inf, r = -inf, mid, ans, f; bool bfs(int x, int y, int maxn) //判断mid是否可行的bfs { queue<pair<int, int> > q; q.push(make_pair(x, y)); //STL里的pair，个人认为要方便一些 vis[x][y] = 1; while(q.size()) { //以下就是bfs板子 int xx = q.front().first; int yy = q.front().second; q.pop(); for(int i = 1; i <= 4; i++) { int nx = xx + dx[i]; int ny = yy + dy[i]; if(nx < 1 || nx > n || yy < 1 || yy > m || vis[nx][ny] || p[nx][ny] > maxn) continue; //不可行（越界、已访问、伤害过大）的直接跳过 vis[nx][ny] = 1; if(nx == n) return 1; //到了，返回1 else q.push(make_pair(nx, ny)); } } return 0; //没有搜到，返回0 } int main() { n = get(), m = get(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { p[i][j] = get(); r = max(r, p[i][j]); l = min(l, p[i][j]); } } while(l <= r) { //二分答案模板 mid = (l + r) >> 1; f = 0; memset(vis, 0, sizeof(vis)); //重置数组 if(bfs(1, 1, mid)) r = mid - 1, ans = mid; //如果这个mid可行，说明可能还能再小，于是更新答案 + 缩小范围 else l = mid + 1; //mid此不可行，说明不可能再小，也缩小范围，不更新答案 } printf("%d", ans); return 0; }
- 1
