問題文の条件の否定を考えて、答えが No になる条件を考えます。

答えが No となるための必要十分条件は、上下左右に隣り合う \(2\) つのマスで、

• 異なる州である
• 同じ色で塗られている
  

を両方満たすものが存在することです。

よって、隣り合うマスを全探索すれば答えを求めることができます。
細かい点は実装例も参考にしてください。

C++の実装例

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

void NO(){
    cout<<"No"<<endl;
    exit(0);//プログラムを終了する
}
signed main(){
    ll h,w,n;cin>>h>>w>>n;
    ll a[h][w];
    for(int i=0;i<=h-1;i++){
        for(int j=0;j<=w-1;j++){
            cin>>a[i][j];
        }
    }
    ll c[n+1];
    for(int i=1;i<=n;i++)cin>>c[i];

    for(int i=0;i<=h-1;i++){
        for(int j=0;j<=w-1;j++){
            if(i+1<=h-1 && a[i][j] != a[i+1][j] && c[a[i][j]] == c[a[i+1][j]]){
                NO();
            }
            if(j+1<=w-1 && a[i][j] != a[i][j+1] && c[a[i][j]] == c[a[i][j+1]]){
                NO();
            }
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}