# 11564: 【原1564】深度优先搜索问题

### 题目描述

author: 孙梦璇 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1564

## Description

1. 只能沿上下左右四个方向移动
2. 总代价是没走一步的代价之和
3. 每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积
4. 初始状态为1

## Sample Input

``````1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5
``````

## Sample Output

``````23
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/17.
//

#include <cstdio>

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int height[6][6];
bool flag[6][6];
int minCost;
int X0, Y0, X, Y;

void dfs(int x, int y, int status, int curCost) {
if (curCost >= minCost) return;
if (x == X && y == Y && minCost > curCost) {
minCost = curCost;
return;
}
flag[x][y] = true;
for (int i = 0; i < 4; ++i) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx >= 6 || yy < 0 || yy >= 6 || flag[xx][yy]) continue;
dfs(xx, yy, (height[xx][yy] * status) % 4 + 1, curCost + height[xx][yy] * status);
}
flag[x][y] = false;
}

int main() {
int n;
scanf("%d", &n);
while (n--) {
for (int i = 0; i < 6; ++i) {
for (int j = 0; j < 6; ++j) {
scanf("%d", &height[i][j]);
}
}
scanf("%d%d%d%d", &X0, &Y0, &X, &Y);
flag[X0][Y0] = true;
minCost = 0x7fffffff;
dfs(X0, Y0, 1, 0);
printf("%d\n", minCost);
flag[X0][Y0] = false;
}
return 0;
}
``````

## FineArtz's solution

``````/* 深度优先搜索问题 */
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int a[6][6];
bool v[6][6];
int ans = 0;

bool check(int x, int y){
if (x < 0 || x > 5 || y < 0 || y > 5 || v[x][y]) return false;
else return true;
}

void dfs(int x, int y, int ex, int ey, int cost, int state){
if (x == ex && y == ey){
ans = min(ans, cost);
return;
}
for (int k = 0; k < 4; ++k){
int nextx = x + dx[k];
int nexty = y + dy[k];
if (check(nextx, nexty)){
int newcost = a[nextx][nexty] * state;
int newstate = newcost % 4 + 1;
v[x][y] = true;
dfs(nextx, nexty, ex, ey, cost + newcost, newstate);
v[x][y] = false;
}
}
}

int main(){
int t;
cin >> t;
while (t--){
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
cin >> a[i][j];
memset(v, 0, sizeof(v));
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
v[sx][sy] = true;
ans = 2147483647;
dfs(sx, sy, ex, ey, 0, 1);
cout << ans << endl;
}
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
using namespace std;

constexpr int inf = 1e9;

bool flag[6][6] = { 0 };
int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };
int disData[6][6] = { 0 };
int dfs(int fromx, int fromy, int tox, int toy, int status) {
if (fromx == tox && fromy == toy)
return 0;
//深度优先搜索
flag[fromx][fromy] = true;
int minDis=inf;
for (int i = 0; i < 4; i++) {
if (fromx + dx[i] < 6 && fromx + dx[i] >= 0 && fromy + dy[i] < 6 && fromy + dy[i] >= 0
&&!flag[fromx+dx[i]][fromy+dy[i]]) {
int dis = disData[fromx + dx[i]][fromy + dy[i]] * status,
ans = dfs(fromx + dx[i], fromy + dy[i], tox, toy, dis % 4 + 1)+dis;
if (minDis > ans) minDis = ans;
}
}
//回溯
flag[fromx][fromy] = false;
return minDis;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);

int n;
cin >> n;

for (; n > 0; n--) {

int fromx, fromy, tox, toy;
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
cin >> disData[i][j];
cin >> fromx >> fromy >> tox >> toy;

//深度优先搜索
cout << dfs(fromx, fromy, tox, toy, 1) << endl;
}

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

int x0, y0, x1, y1, chessboard[10][10] = {-10}, minCost = 2147483647;
bool visited[10][10] = {0};

void visit(int, int, int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

for (int m = 0; m < n; m++) {
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
cin >> chessboard[i][j];
}
}
cin >> x0 >> y0 >> x1 >> y1;
visit(x0, y0, 0, 1);
cout << minCost << '\n';
}
}

void visit(int x0, int y0, int cost, int status) {
if (minCost > cost) {
if (x0 == x1 && y0 == y1) {
minCost = cost;
return;
} else {
int x2 = x0 - 1, y2 = y0;
if (x2 >= 0 && x2 < 6 && !visited[x2][y2]) {
int costTmp = status * chessboard[x2][y2];
visited[x2][y2] = 1;
visit(x2, y2, cost + costTmp, costTmp % 4 + 1);
visited[x2][y2] = 0;
}
x2 = x0 + 1, y2 = y0;
if (x2 >= 0 && x2 < 6 && !visited[x2][y2]) {
int costTmp = status * chessboard[x2][y2];
visited[x2][y2] = 1;
visit(x2, y2, cost + costTmp, costTmp % 4 + 1);
visited[x2][y2] = 0;
}
x2 = x0, y2 = y0 - 1;
if (y2 >= 0 && y2 < 6 && !visited[x2][y2]) {
int costTmp = status * chessboard[x2][y2];
visited[x2][y2] = 1;
visit(x2, y2, cost + costTmp, costTmp % 4 + 1);
visited[x2][y2] = 0;
}
x2 = x0, y2 = y0 + 1;
if (y2 >= 0 && y2 < 6 && !visited[x2][y2]) {
int costTmp = status * chessboard[x2][y2];
visited[x2][y2] = 1;
visit(x2, y2, cost + costTmp, costTmp % 4 + 1);
visited[x2][y2] = 0;
}
}
}
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
using namespace std;

bool visited[6][6];
int MAP[6][6];
int end_x, end_y;
int cost_ans = INT_MAX;

void dfs(int x, int y, int status, int cost) {
static int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
if (cost > cost_ans) return;
if (x == end_x && y == end_y) {
cost_ans = min(cost_ans, cost);
return;
}
for (int d = 0; d < 4; d++) {
int _x = x + dir[d][0];
int _y = y + dir[d][1];
if (_x >= 0 && _y >= 0 && _x < 6 && _y < 6) {
if (!visited[_x][_y]) {
visited[_x][_y] = true;
int _cost = status * MAP[_x][_y];
dfs(_x, _y, _cost % 4 + 1, cost + _cost);
visited[_x][_y] = false;
}
}
}
}
int main() {
int N;
int sx, sy;
scanf("%d", &N);
for (int t = 0; t < N; t++) {
memset(visited, 0, sizeof(visited));
cost_ans = INT_MAX;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
scanf("%d", &MAP[i][j]);
}
}
scanf("%d%d%d%d", &sx, &sy, &end_x, &end_y);
dfs(sx, sy, 1, 0);
printf("%d\n", cost_ans);
}
return 0;
}
``````