1.17 刷题

1 思路

P1331 海战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 本题难点主要是如何分辨哪些穿是相撞而产生无效，哪些是有效
• 很容易想到的是，不论是bfs还是dfs都可以轻松全部搜掉，只需要简单的遍历所有点，然后套板子即可
• 但是这是无法排除无效情况的，也就是相撞的情况
• 推敲一下，发现其实就只有4种情况会无效

• 那么只要写个判断函数就可以排除这四种情况
• 即只需要dfs搜索+判断即可解决这道题

2 代码

#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 1e3 + 10;
int m[N][N];
bool str[N][N];
int r, c, ans;
int dx[] = {0, 1, 1};
int dy[] = {1, 0, 1};

int Judge(int x, int y) {
    int d1 = m[x][y];
    int d2 = m[x + 1][y];
    int d3 = m[x][y + 1];
    int d4 = m[x + 1][y + 1];
    // for(int i = 0; i < 2; i++) {
    //    for(int j = 0; j < 2; j++) {
    //       int nowx = x + dx[i];
    //       int nowy = y + dy[i];
    //       if(nowx <= c && nowy <= r) {
    //          if(m[nowx][nowy] == 1) {
    //             str[nowx][nowy] = 1;
    //          } else {
    //             return -1;
    //          }
    //       }
    //    }
    // }
    if(d1 == 1 && d2 == 1 && d3 == 1 && d4 == 0) return -1;
    if(d1 == 1 && d4 == 1 && d3 == 1 && d2 == 0) return -1;
    if(d1 == 1 && d2 == 1 && d4 == 1 && d3 == 0) return -1;
    if(d4 == 1 && d2 == 1 && d3 == 1 && d1 == 0) return -1;
    return 1;
}

int po() {
    for(int i = 1; i <= r; i++) {
       for(int j = 1; j <= c; j++) {
          int pan = Judge(i,j);
          if(pan == -1) {
             cout<<"Bad placement."<<endl;
             return -1;
          }
       }
    }
    return 0;
}

void dfs(int x, int y) {
    for(int i = 0; i < 3; i++) {
       int nowx = x + dx[i];
       int nowy = y + dy[i];
       if(m[nowx][nowy] == 1 && str[nowx][nowy] == false) {
          str[nowx][nowy] = true;

          dfs(nowx, nowy);
       }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(m, 0, sizeof(m));
    memset(str, false, sizeof(str));


    cin>>r>>c;

    for(int i = 1;i <= r; i++) {
       for(int j = 1;j <= c; j++) {
          char s;
          cin>>s;
          if(s == '#') {
             m[i][j] = 1;
          }
       }
    }

    int k = po();
    if(k == -1) return 0;

    memset(str, false, sizeof(str));
    for(int i = 1;i <= r; i++) {
       for(int j = 1;j <= c; j++) {
          if(m[i][j] == 1 && str[i][j] == false) {
             str[i][j] = true;
             dfs(i, j);
             ans++;
          }
       }
    }

    cout<<"There are "<<ans<<" ships.";

    return 0;

}

import java.util.Scanner;

public class Main {
    static final int N = 1010;
    static int[][] m = new int[N][N];
    static boolean[][] str = new boolean[N][N];
    static int r, c, ans;
    static int[] dx = {0, 1, 1};
    static int[] dy = {1, 0, 1};

    public static int Judge(int x, int y) {
        int d1 = m[x][y];
        int d2 = m[x + 1][y];
        int d3 = m[x][y + 1];
        int d4 = m[x + 1][y + 1];

        if(d1 == 1 && d2 == 1 && d3 == 1 && d4 == 0) return -1;
        if(d1 == 1 && d4 == 1 && d3 == 1 && d2 == 0) return -1;
        if(d1 == 1 && d2 == 1 && d4 == 1 && d3 == 0) return -1;
        if(d4 == 1 && d2 == 1 && d3 == 1 && d1 == 0) return -1;
        return 1;
    }

    public static int po() {
        for(int i = 1; i <= r; i++) {
            for(int j = 1; j <= c; j++) {
                int pan = Judge(i,j);
                if(pan == -1) {
                    System.out.println("Bad placement.");
                    return -1;
                }
            }
        }
        return 0;
    }

    public static void dfs(int x, int y) {
        for(int i = 0; i < 3; i++) {
            int nowx = x + dx[i];
            int nowy = y + dy[i];
            if(m[nowx][nowy] == 1 && str[nowx][nowy] == false) {
                str[nowx][nowy] = true;

                dfs(nowx, nowy);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);


        r = scanner.nextInt();
        c = scanner.nextInt();

        for(int i = 1;i <= r; i++) {
            String s1 = scanner.next();
            for(int j = 1;j <= c; j++) {
                char s;
                s = s1.charAt(j - 1);
                if(s == '#') {
                    m[i][j] = 1;
                }
            }
        }

        int k = po();
        if(k == -1) return;

        for(int i = 1;i <= r; i++) {
            for(int j = 1;j <= c; j++) {
                if(m[i][j] == 1 && str[i][j] == false) {
                    str[i][j] = true;
                    dfs(i, j);
                    ans++;
                }
            }
        }


        System.out.println("There are " + ans + " ships.");
        return;
    }

}