题目链接：点击打开链接
题目大意：跑毒，跑到安全区，每个地方有敌人，输出路线经过的最少敌人的数量；-1是起点。 -2是安全区
输入
5
6 6 0 -2 3
4 2 1 2 1
2 2 8 9 7
8 1 2 1 -1
9 7 2 1 2
输出
9
输入
5
62 33 18 -2 85
85 73 69 59 83
44 38 84 96 55
-1 11 90 34 50
19 73 45 53 95
输出
173
深搜，或广搜。还有用最短路径做的。
DFS超时代码
好好理解那个dfs里面的参数
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f;
int sx, sy, ex, ey, n, ans;
int mp[120][120];
int vis[120][120];
int des[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
bool judge(int x, int y) {//越界
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
if(vis[x][y])//访问过
return false;
return true; //竟然忘写了
}
void dfs(int x, int y, int cost) {
if(mp[x][y] == -2) {
ans = min(ans, cost);//到达安全区，取最少的敌人数
return;
}
for(int i = 0; i < 4; i++) {//四个方向遍历
int tempx = x + des[i][0];
int tempy = y + des[i][1];
if(judge(tempx, tempy)) {
vis[tempx][tempy] = 1;//标记
dfs(tempx, tempy, cost+mp[tempx][tempy]);//搜，注意那个重要参数
vis[tempx][tempy] = 0;//回溯
}
}
}
int main() {
while(~scanf("%d", &n)) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &mp[i][j]);
if(mp[i][j] == -1) {//记录
sx = i;
sy = j;
}
}
}
ans = INF;//因为可能有好几条路
memset(vis, 0, sizeof(vis));
dfs(sx, sy, 0);//这里注意，dfs的特点。参数中有一个是将要累加得到的结果
printf("%d
", ans+2);//因为最后的-2也加了
}
}BFS+优先级队列
可能会有疑问，为什么得用优先级队列，我看了几道题，感觉涉及时间（权）不同的，用优先级队列。而对于一般的没什么和值有关的，就不需要优先级队列。 AC代码
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n;
int mp[120][120];
int vis[120][120];
int des[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
bool judge(int x, int y) {
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
if(vis[x][y])
return false;
return true;
}
struct node{
int x;
int y;
int w;
bool friend operator < (node a, node b) {//排序规则
return a.w > b.w;
}
}Node, temptop;
int bfs(int x, int y) {
int ans = -1;//结果
Node.x = x;
Node.y = y;
Node.w = 0;
priority_queue<node> pq;
pq.push(Node);
vis[x][y] = 1;
while(!pq.empty()) {
temptop = pq.top();
pq.pop();
for(int i = 0; i < 4; i++) {
Node.x = temptop.x + des[i][0];
Node.y = temptop.y + des[i][1];
if(judge(Node.x, Node.y)) {
if(mp[Node.x][Node.y] == -2) {//到了终点，肯定是最优解。
ans = temptop.w;
break;
}
vis[Node.x][Node.y] = 1;//访问过
Node.w = temptop.w + mp[Node.x][Node.y];//累加指
pq.push(Node);//入队
}
}
if(ans != -1)
break;
}
return ans;
}
int sx, sy;
int main() {
while(~scanf("%d", &n)) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &mp[i][j]);
if(mp[i][j] == -1) {
sx = i;
sy = j;
}
}
}
memset(vis, 0, sizeof(vis));
printf("%d
", bfs(sx, sy));
}
}
BFS+ 最短路
思路很灵活，没见过这样的
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MAX = 120;
const int INF = 0x3f3f3f3f;
int n;
int mp[120][120];
int d[120][120];//距离数组
int des[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
bool judge(int x, int y) {
if(x < 0 || x >= n || y < 0 || y >= n)
return false;
return true;
}
struct node{
int x;
int y;
}Node, temptop;
int sx, sy, ex, ey;
int bfs(int x, int y) {
int ans = -1;
Node.x = x;
Node.y = y;
queue<node> pq;
pq.push(Node);
d[x][y] = 0;
while(!pq.empty()) {
temptop = pq.front();
pq.pop();
for(int i = 0; i < 4; i++) {
Node.x = temptop.x + des[i][0];
Node.y = temptop.y + des[i][1];
if(judge(Node.x, Node.y)) {//就像最短路，能更新就更新
if(d[Node.x][Node.y] > d[temptop.x][temptop.y] + mp[temptop.x][temptop.y]) {
d[Node.x][Node.y] = d[temptop.x][temptop.y] + mp[temptop.x][temptop.y];
pq.push(Node);//入队
}
}
}
}
return d[ex][ey];//返回终点值
}
int main() {
while(~scanf("%d", &n)) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &mp[i][j]);
if(mp[i][j] == -1) {
mp[i][j] = 0;//很重要
sx = i;
sy = j;
}
if(mp[i][j] == -2) {//也存安全区的位置
mp[i][j] = 0;//很重要
ex = i;
ey = j;
}
}
}
fill(d[0], d[0] + MAX*MAX, INF);//初始化
printf("%d
", bfs(sx, sy));
}
}