剪纸游戏

#include <stdio.h>
#include <stdlib.h>

//来，这次得好好写单链表的队列。
//怎么判断是不是长方形：对 component_cells 列表中的所有坐标，找到它们行和列的最大值与最小值，从而确定这个图案的边界框 (Bounding Box)。
//找到最小最大的xy值计算边界框的理论面积，对比走过的格子是不是那么多就行。

//BFS需要队列，但是c语言需要自己写,恶心
typedef struct position{   //单链表队列
    int x;
    int y;
    int bushu;   //这个问题用不到最短路径的步数统计
    struct position*next;
}position,*positionlink;

positionlink queue;//队列

//入队列
void queue_push(positionlink* queue,positionlink temp){
    if (*queue==NULL) {  //判断指向的内容是否空队列
        *queue=temp;
    }else {
        positionlink p=(*queue);
        while (p->next!=NULL) {
            p=p->next;
        }
        p->next=temp;
    }
}

//出队列;
positionlink queue_pop(positionlink* queue)  //传队列的指针进来才不会是复制
{
    if(*queue==NULL){
        return *queue;
    }else {
        positionlink temp=*queue;
        *queue=(*queue)->next;
        temp->next=NULL;    //卧槽，原来是忘记断开连接了
        return  temp;
    }
}

//判断队列是否为空.为1时是空队列
int is_empty_queue(positionlink *queue)
{
    return (*queue)==NULL;
}

//显示队列情况
void show_queue(positionlink queue)
{
    positionlink t=queue;
    while(t!=NULL)
    {
        printf("x=%d,y=%d ---",t->x,t->y);
        t=t->next;//应该是t-next
    }
    printf("\n");
    
    return;
}

// 创建新节点，我丢不能利用栈上创建的节点加入队列啊，堆栈不能混用，因为栈上的局部变量会消失啊
positionlink create_node(int x, int y) {
    positionlink new_node = malloc(sizeof(position));
    if (new_node == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    new_node->x = x;
    new_node->y = y;
    new_node->bushu = 0;
    new_node->next = NULL;
    return new_node;
}
    
int main() {
    
    queue=NULL;  //初始化队列
    //测试队列
    // position temp={
    //     .x=6,
    //     .y=5,
    //     .bushu=10,
    //     .next=NULL
    // };

    // queue_push(&queue, &temp);
    // printf("empty=%d\n",is_empty_queue(queue));
    // positionlink  t=queue_pop(&queue);
    // printf("x=%d y=%d bushu=%d\n",t->x,t->y,t->bushu);
    
    //读取方格纸
    int n,m;
    scanf("%d %d",&n,&m);
    char **fangge=malloc(sizeof(char*)*n);
    

    for (int i=0;i<n; i++) {
        fangge[i]=malloc(sizeof(char)*(m+1));//加1保住/0
        scanf("%s",fangge[i]);
        //printf("%s\n",fangge[i]);
    }
    int changfang_count=0; //记录长方形个数
    //开始找图案
    for (int i=0; i<n; i++) {  //x轴
        for(int j=0;j<m;j++)
        {
            if(fangge[i][j]=='.')
            {
                //找图案，记录最小最大xy轴,和走过的方格个数
                int min_x=m,min_y=n,max_x=0,max_y=0,geshu=1;
                //初始位置入队列
                position temp={
                        .x=j,  //x是横的那个吧
                        .y=i,
                        .bushu=0,//本题好像不用记最短路径
                        .next=NULL
                };
                fangge[i][j]='*'; //阻塞
                queue_push(&queue,&temp);
                while (is_empty_queue(&queue)==0) {  //不为空表示队列没遍历完                    
                    positionlink tou=queue_pop(&queue); //拿到队列的头
                    //printf("取出的位置（%d,%d）\n",tou->x,tou->y);
                    //show_queue(queue);
                    //记录最小最大xy值，和走过的步数
                    if (tou->x<min_x) {
                        min_x=tou->x;
                    }
                    if (tou->x>max_x) {
                        max_x=tou->x;
                    }
                    //记录最小最大xy值
                    if (tou->y<min_y) {
                        min_y=tou->y;
                    }
                    if (tou->y>max_y) {
                        max_y=tou->y;
                    }

                    //看看往上下左右能不能走
                    if (tou->x-1>=0&&fangge[tou->y][tou->x-1]=='.') {     //往左                       
                        geshu++;//走过的个数
                        positionlink temp=create_node(tou->x-1, tou->y);
                        queue_push(&queue, temp);
                        fangge[tou->y][tou->x-1]='*';  //标记阻塞
                    }
                    if (tou->x+1<m&&fangge[tou->y][tou->x+1]=='.') {     //往右                       
                        geshu++;//走过的个数
                        positionlink temp=create_node(tou->x+1, tou->y);
                        queue_push(&queue, temp);
                        fangge[tou->y][tou->x+1]='*';  //标记阻塞
                    }
                    if (tou->y-1>=0&&fangge[tou->y-1][tou->x]=='.') {     //往上                       
                        geshu++;//走过的个数
                        positionlink temp=create_node(tou->x, tou->y-1);
                        queue_push(&queue, temp);
                        fangge[tou->y-1][tou->x]='*';  //标记阻塞
                    }
                    if (tou->y+1<n&&fangge[tou->y+1][tou->x]=='.') {     //往下                       
                        geshu++;//走过的个数
                        positionlink temp=create_node(tou->x, tou->y+1);
                        queue_push(&queue, temp);
                        fangge[tou->y+1][tou->x]='*';  //标记阻塞
                    }
                    
                     
                }

                //遍历结束后，计算是不是长方形
                int d=max_x-min_x+1;  //底的长度
                int h=max_y-min_y+1;  //高
                if (d*h==geshu) {       //理论长方形面积是否等于走过的方格个数
                    changfang_count++;
                }

            }else if (fangge[i][j]=='*') {  //跳过
                continue;
            }
        }
    }

    printf("%d",changfang_count);


    return 0;
}