kingsleykingsley @ 2024-07-18 20:47:49

#include <iostream>
using namespace std;

int a[50][50];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(a[i][j] == 1) continue;
            bool f1 = 0, f2 = 0, f3 = 0, f4 = 0;
            for(int k = j; k <= n; k++) if(a[i][k] == 1){f1 = 1; break;}
            for(int k = i; k <= n; k++) if(a[k][j] == 1){f2 = 1; break;}
            for(int k = j; k >= 1; k--) if(a[i][k] == 1){f3 = 1; break;}
            for(int k = i; k >= 1; k--) if(a[k][j] == 1){f4 = 1; break;}
            if(f1 && f2 && f3 && f4) a[i][j] = 2;
        } 
    }
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= n; j++) cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}

by SwethessPotion @ 2024-07-18 20:51:08

啊？这道题不是广搜吗？

by SwethessPotion @ 2024-07-18 20:52:25

@kingsleykingsley AC Code:

#include <bits/stdc++.h>
using namespace std;

const int N = 35;
bool vis[N][N];
int arr[N][N], n;
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

queue<pair<int, int> > q;
void bfs(int i, int j)
{
    vis[i][j] = true;
    q.push({i, j});
    while (!q.empty())
    {
        for (int i = 1; i <= 4; i++)
        {
            int xx = q.front().first + dx[i], yy = q.front().second + dy[i];
            if (1 <= xx && xx <= n && 1 <= yy && yy <= n && arr[xx][yy] == 0 && !vis[xx][yy])
            {
                vis[xx][yy] = true;
                q.push({xx, yy});
            }
        }
        q.pop();
    }
}

void input()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {   
            cin >> arr[i][j];
        }
    }
}

void startBfs()
{
    for (int i = 1; i <= n; i++)
    {
        if (arr[i][1] == 0)
        {
            bfs(i, 1);
        }
        if (arr[1][i] == 0)
        {
            bfs(1, i);
        }
        if (arr[n][i] == 0)
        {
            bfs(n, i);
        }
        if (arr[i][n] == 0)
        {
            bfs(i, n);
        }
    }
}

void printAnswer()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (!vis[i][j] && arr[i][j] == 0)
            {
                cout << "2 ";
            }
            else
            {
                cout << arr[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    input();
    startBfs();
    printAnswer();
    return 0;
}

by kingsleykingsley @ 2024-07-18 20:54:41

谢谢谢 已关

by fire_flies @ 2024-07-18 20:55:09

@kingsleykingsley 深搜应该会t掉

by KevinJoshua @ 2024-07-18 20:56:39

@kingsleykingsley 码风有点怪，见谅

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
};
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int n,a[31][31];
queue<node> q;
void bfs(int x,int y)
{
    a[x][y]=0;
    q.push(node{x,y});
    while(!q.empty())
    {
        int xx=q.front().x,yy=q.front().y;
        q.pop();
        for (int i=0;i<4;i++)
        {
            int u=xx+dx[i],v=yy+dy[i];
            if  (u>=1 && u<=n && v>=1 && v<=n && a[u][v]==2)
            {
                if  (a[u][v]==1)
                    break;
                q.push(node{u,v});
                a[u][v]=0;
            }
        }
    }
    return;
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if  (a[i][j]==0)
                a[i][j]=2;
        }
    }
    for (int i=1;i<=n;i++)
    {
        if  (a[i][1]==2)
            bfs(i,1);
        if  (a[i][n]==2)
            bfs(i,n);
        if  (a[1][i]==2)
            bfs(1,i);
        if  (a[n][i]==2)
            bfs(n,i);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            cout<<a[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

by Crab_Tang @ 2024-07-21 17:33:10

@fire_flies t不掉的。剪枝啊，你看我

by fire_flies @ 2024-07-21 18:11:26

@Crab_Tang 已懂，新学剪枝

by wongyd @ 2024-07-23 16:55:38

@kingsleykingsley 方案总和用dsf，最短路径用bsf