Skip to content

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

题目

题目描述

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

Description

有一个6*6的棋盘,每个棋盘上都有一个数值,现在又一个起始位置和终止位置,请找出一个从起始位置到终止位置代价最小的路径:

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

每走一步,状态按如下公式变化:(走这步的代价%4)+1。

Input Format

第一行有一个正整数n,表示有n组数据。

每组数据一开始为6*6的矩阵,矩阵的值为大于等于1小于等于10的值,然后四个整数表示起始坐标和终止坐标。

Output Format

输出最小代价

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;
}