剪纸游戏

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

bool check_Rectangle(int &count, int &min_x, int &min_y, int &max_x, int &max_y, vector<string> &maze) {
    int rect_area = (max_x - min_x + 1) * (max_y - min_y + 1);
    if(rect_area != count) {
        return false;
    }

    for (int i = min_x; i <= max_x; i++) {
        for(int j = min_y; j < max_y; j++) {
            if(maze[i][j] != '.') {
                return false;
            }
        }
    }
    return true;
}

bool bfs(int i, int j, vector<string>& maze, vector<vector<bool>> &visited,
         int n, int m) {
    queue<pair<int, int>> q;
    q.push({i, j});
    visited[i][j] = true;

    //最小的坐标和最大的坐标
    int min_x = i, max_x = i, min_y = j, max_y = j;
    int count = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        count ++;
        min_x = min(min_x, x);
        min_y = min(min_y, y);
        max_x = max(max_x, x);
        max_y = max(max_y, y);

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m &&
                visited[nx][ny] == false && maze[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
            }
        }
    }
    if(check_Rectangle(count, min_x, min_y, max_x, max_y, maze)) {
        return true;
    }else {
        return false;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }

    int sx = 0, sy = 0;
    int ex = n - 1, ey = m - 1;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int rectangle_count = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == '.' && visited[i][j] == false) {
                if (bfs(i, j, maze, visited, n, m)) {
                    rectangle_count++;
                }
            }
        }
    }
    cout << rectangle_count << endl;

}
// 64 位输出请用 printf("%lld")

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

/*
    for n // 从左往右
        for m // 从上往下
            BFS(i,j) 

    BFS(i,j)时，k[i][j]应该是长方形的左上角，记录最右的下标max_i、最下的下标max_j和'.'的数量num，判断(max_i+1-i)*(max_j+1-j) == num，但是有部分样例没通过。
    后面加上记录 min_i，min_j，然后判断(max_i+1 -min_i)*(max_j+1 -min_j) == num就都通过了。
*/
package main

import (
	"fmt"
)

type Node struct{
    i,j int
}

func main() {
    var n, m int
    fmt.Scanf("%d %d", &n, &m)
    var k = make([][]byte, n)
    var v = make([][]bool, n)
    var s string
    for i:=0;i<n;i++{
        k[i] = make([]byte, m)
        v[i] = make([]bool, m)
        fmt.Scanf("%s", &s)
        k[i] = []byte(s)
    }

    var result, num, max_i, max_j, ni, nj, min_i, min_j int
    var queue []Node
    var cur Node
    dist := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}

    var BFS func(i, j int)
    BFS = func(i,j int){
        queue = []Node{{i,j}}
        for len(queue) > 0{
            cur = queue[0]
            queue =queue[1:]

            for _, d := range dist{
                ni = cur.i + d[0]
                nj = cur.j + d[1]
                if ni<0 || ni>=n ||nj<0||nj>=m||v[ni][nj]||k[ni][nj]=='*'{
                    continue
                }
                v[ni][nj] = true
                num++
                queue = append(queue, Node{ni,nj})
                if ni > max_i {
                    max_i = ni
                }
                if ni < min_i {
                    min_i = ni
                }
                if nj > max_j {
                    max_j = nj
                }
                if nj < min_j{
                    min_j = nj
                }
            }
        }
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if k[i][j] == '.' && !v[i][j]{
                v[i][j] = true
                max_i = i
                max_j = j
                min_i = i
                min_j = j
                num = 1
                BFS(i,j)
                if (max_i+1 -min_i)*(max_j+1 -min_j) == num {
                    result++
                }
            }
        }
    }
    fmt.Print(result)
}

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

//上下左右
int a,b,c,d;

int dfs(vector<string>& grid, int i, int j)
{
    int n = grid.size();
    int m = grid[0].size();
    if (i < 0 || i==n || j<0 || j==m || grid[i][j] != '.')
    {
        return 0;
    }
    int ans = 1;
    grid[i][j] = '*';
    a = max(a,i);
    b = min(b,i);
    c = min(c,j);
    d = max(d,j);
    ans += dfs(grid, i+1, j);
    ans += dfs(grid, i-1, j);
    ans += dfs(grid, i, j+1);
    ans += dfs(grid, i, j-1);
    return ans;
}
int main() {
    int n,m;
    cin >> n >> m;
    vector<string> grid(n);
    for (string& s : grid)
    {
        cin >> s;
    }

    int cnt = 0;
    for (int i = 0; i<n; ++i)
    {
        for (int j = 0; j<m; ++j)
        {
            if (grid[i][j] == '.')
            {
                a = d = INT_MIN;
                b = c = INT_MAX;
                int area = dfs(grid,i,j);
                if (area == (a-b+1)*(d-c+1))
                {
                    cnt++;
                }
            }
        }
    }
    cout << cnt;

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
 int n,m;
vector<string> s;
vector<vector<bool>> visited;
bool bfs(int a,int b)
{
    int maxx=0,mayy=0;
    int mixx=1e9,miyy=1e9;
    queue<pair<int,int>> q;
    q.push({a,b});
    int count=1;
    visited[a][b]=true;
    while(!q.empty())
    {
        auto [x,y]=q.front();
        q.pop();
        maxx=max(maxx,x);
        mayy=max(mayy,y);
        mixx=min(mixx,x);
        miyy=min(miyy,y);
        for(int i=0;i<4;i++)
        {
            int nx=dx[i]+x;
            int ny=dy[i]+y;
            if(nx>=1 && nx<=n && ny>=1 && ny<=m &&!visited[nx][ny] &&s[nx][ny]=='.')
            {
                visited[nx][ny]=true;
                q.push({nx,ny});
                count++;
            }
        }
    }
    int area = (maxx - mixx + 1) * (mayy - miyy + 1);
    return count == area;
    
}




int main() {
   
    int ans=0;
    cin>>n>>m;
    s.resize(n+1);
    visited.resize(n+1,vector<bool>(m+1,false));
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=' '+s[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='.' && !visited[i][j])
            {
             bool f=bfs(i,j);
                if(f) ans++;
            }
        }
    }
    cout<<ans<<endl;
     
}