-5

Ủa sao không ai làm bài mình vậy :)))

lamnhb111 đã đăng vào 15, Tháng 9, 2025, 20:41

Dưới đây là bài toán được đề cập đến trong tiêu đề, nếu ai có lời giải thì hãy comment bằng cú pháp:

<tên>
dùng dấu "```" ở hai đầu để viết được code vào đó:
VD:
Nguyen Van A:
"```"
code
"```"

*Lưu ý: Dấu ``` để riêng ra ngoài và không cho vào ngoặc hay để trên 1 dòng, phải làm đúng như trên thì code mới hiện thị chuẩn format khi gõ được

Dưới đây là đề bài:

ĐẾM ĐƯỜNG ĐI ĐỐI XỨNG:

Cho một ma trận A kích thước N x N (1 ≤ N ≤ 500) Các hàng đánh số từ 1 đến N từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái qua phải. Ô nằm trên hàng i, cột j gọi là ô A[i][j] có giá trị là các chữ cái latin in hoa. Xét các đường đi từ ô (1; 1) đến ô (N; N) mà trong một bước đi bạn chỉ được phép di chuyển xuống dưới hoặc qua phải. Mỗi đường đi được đại diện bởi một xâu được tạo thành bằng cách viết liên tiếp các kí tự trên đường đi. Hãy đếm số lượng đường đi có xâu đại diện là xâu đối xứng.

Input:

Dòng đầu tiên là số nguyên N là kích thước của ma trận.
N dòng tiếp theo mỗi dòng gồm một xâu đại diện cho hàng thứ i của ma trận.

Output:

Gồm một dòng duy nhất là số lượng đường đi có xâu đại diện là xâu đối xứng sau khi chia lấy dư cho (10^9) + 7

Sample Input:

4
ABCD
BXZX
CDXB
WCBA

Sample Output:

12

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    lamnhb111  đã bình luận lúc 12, Tháng 10, 2025, 13:05

    lol


  • -2
    pika68267  đã bình luận lúc 24, Tháng 9, 2025, 13:21 ← chỉnh sửa

    Mai Phuc Thinh:

    "```"

    def solve():
    from collections import Counter
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = [input().strip() for _ in range(N)]

    dp = Counter()
    if a[0][0] == a[-1][-1]:
        dp[(0, N-1)] = 1     # (row_top, row_bottom)

    for step in range(N-1):
        nxt = Counter()
        for r1, r2 in dp:
            c1 = step - r1
            c2 = (2*N-2-step) - r2
            for dr1, dc1 in ((1,0),(0,1)):
                nr1, nc1 = r1+dr1, c1+dc1
                if nr1>=N or nc1>=N: continue
                for dr2, dc2 in ((-1,0),(0,-1)):
                    nr2, nc2 = r2+dr2, c2+dc2
                    if nr2&lt;0 or nc2&lt;0: continue
                    if a[nr1][nc1] == a[nr2][nc2]:
                        nxt[(nr1,nr2)] += dp[(r1,r2)]
        dp = nxt

    ans = 0
    for r1, r2 in dp:
        c1 = (N-1) - r1
        c2 = (N-1) - r2
        if r1==r2 and c1==c2: ans += dp[(r1,r2)]
        elif abs(r1-r2)+abs(c1-c2)==1: ans += dp[(r1,r2)]
    print(ans)
    solve()

    "```"


    • 0
      lamnhb111  đã bình luận lúc 25, Tháng 9, 2025, 14:56

      bạn ơi, bạn dùng NNLT j vậy, mình thấy lỗi syntax ở dòng số 22 nha


      • -1
        pika68267  đã bình luận lúc 12, Tháng 10, 2025, 5:48

        AI đó bạn :)