矩阵剪刀石头布

GitHub跳转原题关系图返回列表

每天基于旧矩阵检查四邻格是否存在克制者，再同步更新剪刀石头布领地。

OJ: noi_openjudge

题目 ID: ch0108-16

难度:普及-

标签:矩阵模拟python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. Python代码
  7. C++代码
    1. 复杂度
    2. 总结

题意

在二维剪刀石头布中，若四邻格存在能战胜当前生命的种类，当前格在当天结束后被占领。

思路

字典记录每种生命的克制者。每一天复制旧网格，判断每个格的四邻格是否存在克制者，所有判断结束后同步换成新网格。

代码

cpp
#include<iostream>
using namespace std;
char a[101][101],b[101][101];
int main()
{
    int r,c,n,i,j;
    cin>>r>>c>>n;
    for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
            cin>>a[i][j];
    for(int d=1;d<=n;d++)
    {
        for(i=1;i<=r;i++)
            for(j=1;j<=c;j++)
                b[i][j]=a[i][j];
        for(i=1;i<=r;i++)
            for(j=1;j<=c;j++)
            {
                if(b[i][j]=='R'&&b[i][j+1]=='P'||b[i][j]=='R'&&b[i][j-1]=='P'||b[i][j]=='R'&&b[i-1][j]=='P'||b[i][j]=='R'&&b[i+1][j]=='P')a[i][j]='P';
                if(b[i][j]=='S'&&b[i][j+1]=='R'||b[i][j]=='S'&&b[i][j-1]=='R'||b[i][j]=='S'&&b[i-1][j]=='R'||b[i][j]=='S'&&b[i+1][j]=='R')a[i][j]='R';
                if(b[i][j]=='P'&&b[i][j+1]=='S'||b[i][j]=='P'&&b[i][j-1]=='S'||b[i][j]=='P'&&b[i-1][j]=='S'||b[i][j]=='P'&&b[i+1][j]=='S')a[i][j]='S';
            }
    }

    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
            cout<<a[i][j];
        cout<<endl;
    }
    return 0;	
}

复杂度

总结

Python代码

python
row_count, column_count, days = map(int, input().split())
grid = [list(input().strip()) for _ in range(row_count)]
defeated_by = {"R": "P", "S": "R", "P": "S"}

for _ in range(days):
    next_grid = [row[:] for row in grid]
    for row in range(row_count):
        for column in range(column_count):
            winner = defeated_by[grid[row][column]]
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                neighbor_row, neighbor_column = row + dx, column + dy
                if 0 <= neighbor_row < row_count and 0 <= neighbor_column < column_count and grid[neighbor_row][neighbor_column] == winner:
                    next_grid[row][column] = winner
                    break
    grid = next_grid

for row in grid:
    print("".join(row))

C++代码

cpp
#include<iostream>
using namespace std;
char a[101][101],b[101][101];
int main()
{
    int r,c,n,i,j;
    cin>>r>>c>>n;
    for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
            cin>>a[i][j];
    for(int d=1;d<=n;d++)
    {
        for(i=1;i<=r;i++)
            for(j=1;j<=c;j++)
                b[i][j]=a[i][j];
        for(i=1;i<=r;i++)
            for(j=1;j<=c;j++)
            {
                if(b[i][j]=='R'&&b[i][j+1]=='P'||b[i][j]=='R'&&b[i][j-1]=='P'||b[i][j]=='R'&&b[i-1][j]=='P'||b[i][j]=='R'&&b[i+1][j]=='P')a[i][j]='P';
                if(b[i][j]=='S'&&b[i][j+1]=='R'||b[i][j]=='S'&&b[i][j-1]=='R'||b[i][j]=='S'&&b[i-1][j]=='R'||b[i][j]=='S'&&b[i+1][j]=='R')a[i][j]='R';
                if(b[i][j]=='P'&&b[i][j+1]=='S'||b[i][j]=='P'&&b[i][j-1]=='S'||b[i][j]=='P'&&b[i-1][j]=='S'||b[i][j]=='P'&&b[i+1][j]=='S')a[i][j]='S';
            }
    }

    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
            cout<<a[i][j];
        cout<<endl;
    }
    return 0;	
}

复杂度

设天数为 dd，时间复杂度为 O(drc)O(drc)，额外空间复杂度为 O(rc)O(rc)。

总结

同一时刻发生的格子变化必须同步更新。