結果

問題 No.13 囲みたい！
ユーザー newlife171128
提出日時 2018-02-22 22:02:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,506 bytes
コンパイル時間 1,150 ms
コンパイル使用メモリ 160,208 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-03 03:53:11
合計ジャッジ時間 1,783 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include "bits/stdc++.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <map>
#include <unordered_map>
#include <string.h>
#include <utility>

typedef long long ll;
const int INF = 1e8;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;

typedef pair<int, int> P;

int field[101][101];
bool visited[101][101];
int w, h, now;

int xt[] = { 1, 0, -1, 0 };
int yt[] = { 0, 1, 0, -1 };
bool judge = false;
bool dfs(int y, int x, int pre_x, int pre_y) {


	if (visited[y][x]) {
		/*cout << x << " " << y << " " << pre_x << " " << pre_y << endl;*/
		return true;
	}

	visited[y][x] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + xt[i];
		int ny = y + yt[i];

		if (pre_x == nx && pre_y == ny) {
			continue;
		}

		if (nx < w && nx >= 0 && ny < h && ny >= 0 && field[ny][nx] == now) {

			if(dfs(ny, nx, x, y)){
				return true;

			}
		}

	}

	return false;

}

int main() {

	cin >> w >> h;

	int tmp = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> tmp;

			field[i][j] = tmp;
		}
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {

			if (!visited[i][j]) {
				now = field[i][j];

				if(dfs(i, j, -1, -1)){
					judge = true;
				}
			}

		}
	}

	if (judge) {
		cout << "possible" << endl;
	} else {
		cout << "impossible" << endl;
	}

	return 0;
}
0