HD200703 | HD200703

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int n,startx,starty,finx,finy,f[][],a[],b[],c[],d[],v[],dis[][];

int main()

{

    int i,j,k=;

    scanf("%d%d%d%d%d",&n,&startx,&starty,&finx,&finy);

    memset(dis,,sizeof(dis));

    dis[startx][starty]=;

    int l=n*n;

    for(i=;i<=n;i++)

        for(j=;j<=n;j++)

            scanf("%d",&f[i][j]);

    for(i=;i<=n;i++)

    {

        for(j=;j<=n;j++)

        {

            if(i==n)

            {

                if(j==n) break;

                a[k]=i;

                b[k]=j;

                c[k]=i;

                d[k]=j+;

                v[k++]=f[i][j+];

            }

            else

            {

                if(j==n)

                {

                    a[k]=i;

                    b[k]=j;

                    c[k]=i+;

                    d[k]=j;

                    v[k++]=f[i+][j];

                    continue;

                }

                else

                {

                    a[k]=i;

                    b[k]=j;

                    c[k]=i;

                    d[k]=j+;

                    v[k++]=f[i][j+];

                    a[k]=i;

                    b[k]=j;

                    c[k]=i+;

                    d[k]=j;

                    v[k++]=f[i+][j];

                    continue;

                }

            }

        }

    }

    k--;

    for(i=k+;i<=k*;i++)

    {

        a[i]=c[i-k];

        b[i]=d[i-k];

        c[i]=a[i-k];

        d[i]=b[i-k];

        v[i]=f[c[i]][d[i]];

    }

    k*=;

    //for(i=1;i<=k;i++) printf("%d %d %d %d %d\n",a[i],b[i],c[i],d[i],v[i]); printf("%d",k);

    for(i=;i<l;i++)

    {

        int check=;

        for(j=;j<=k;j++)

        {

            if(dis[c[j]][d[j]]>dis[a[j]][b[j]]+v[j])

            {

                dis[c[j]][d[j]]=dis[a[j]][b[j]]+v[j];

                check=;

            }

        }

        if(check==) break;

    }

    /*

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

            printf("%d ",dis[i][j]);

        printf("\n");

    }

    */

    printf("%d",dis[finx][finy]+f[startx][starty]);

    return ;

}

HD200703排雷

难度级别：B；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

一片战场被划分为N行N列小区域，敌我双方各占据其中一个小区域。
根据侦察，敌人派出工兵潜入各区域（包括我方和敌方所在区域）布设了地雷。
现我方侦察兵已经掌握了各片区域的地雷数量。为偷袭敌人，需要寻找一条从我方区域通向敌方区域并且地雷总数最少的路径，执行偷袭任务时,此路净上的地雷都需要排除。
请你编一个名为MIN的程序，计算出偷袭路径最少需要排雷多少个。
说明：排雷总数包括我方和敌方所在区域的地雷数。偷袭路径是由一个个区域连接而成，每个区域只能通向上、下、左、右的4个相邻区域。

输入

输入第一行只有一个数N，表示每行每列区域个数。1<N<30。第二行两个数表示我方区域所在的行和列。第三行两个数表示敌方区域所在的行和列。这四个数均为不超过N的正整数。接下去的N行中，每行有N个数，表示整个战场的地雷分布。每个区域的地雷数均是小于10000的非负整数。

输出

输出中只有一个数，即最小排雷数。

输入示例

4 2 1 3 3 1 1 1 1 2 9 8 3 8 9 4 2 1 2 3 4

输出示例

为什么WA！！！