我又来刷水题了…

vj原题

题目

定义一个二维数组：

int maze[5][5] = {

    0, 1, 0, 0, 0,

    0, 1, 0, 1, 0,

    0, 0, 0, 0, 0,

    0, 1, 1, 1, 0,

    0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

AC代码

#include<stdio.h>
//#include<queue>
//using namespace std;

int maze[5][5];

struct node
{
    int x,y,pre;
}q[100];

//queue <node> que;

void output(int i)
{
    if(q[i].pre != -1)
    {
        output(q[i].pre);
        printf("(%d, %d)\n",q[i].x,q[i].y);
    }
}

void bfs(int x,int y)
{
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,-1,1};
    int front = 0;
    int rear = 1;
    q[front].x = x;
    q[front].y = y;
    q[front].pre = -1;
    //que.push(q[front]);
    while(front < rear)
    {
        for(int i = 0;i<4;i++)
        {
            int nx = q[front].x + dx[i];
            int ny = q[front].y + dy[i];
            //if(nx >= 0 && nx < 5 && ny >= 0  && ny <5 && maze[nx][ny])
            if(nx<0||nx>=5||ny<0||ny>=5||maze[nx][ny])
                continue;
            else
            {
                maze[nx][ny] = 1;
                q[rear].x = nx;
                q[rear].y = ny;
                q[rear].pre = front;
                //que.push(q.[rear]);
                rear++;
            }
            if(nx == 4 && ny == 4)
            {
                output(front);
            }
        }
        front++;
    }
}
int main()
{
    for(int i = 0;i<5;i++)
    {
        for(int j = 0;j<5;j++)
        {
            scanf("%d",&maze[i][j]);
        }
    }
    printf("(0, 0)\n");
    bfs(0,0);
    printf("(4, 4)\n");
}

这题没啥坑……

明天校赛加油💪